[JAVA, App] 6.검색

검색(search)

1.순차검색

• 데이터가 정렬되지 않았을 때 데이터를 앞에서부터 순서대로 검색
• 첫번째 데이터와 마지막 데이터의 검색 시간이 차이가 많이 나고 데이터가 없는 경우 전체 데이터를 확인해야만 없다는 사실을 알 수 있습니다.

2.제어검색

• 데이터가 정렬된 경우 사용하는 검색 방법

1) 이분 검색(Binary Search): 데이터의 중앙값과 비교해서 작으면 왼쪽 크면 오른쪽에 가서 다시 중앙값과 비교하는 방식

2) 피보나치 검색: 피보나치 수열의 값을 이용해서 검색

• 1,1,2,3,5,8,13...(첫번째 와 두번째는 1 세번째 부터는 앞쪽 2개 항의 합)

3) 보간 검색

• 검색 위치를 계산해서 검색
  (검색값 - 최소값) / (최대값 - 최소값) 을 계산한 후 데이터 개수와 곱해서 찾는 방식
• 데이터의 분포가 고르다면 제어검색 중에서 성능이 우수함

4) 이진 트리 검색

• 데이터를 삽입할 때 정렬 하는 것처럼 작으면 왼쪽 크면 오른쪽에 배치해서 검색
• 이진 트리는 만들다 보면 정확하게 반으로 분할 되지는 않습니다.

3.블록 검색

• 블록 단위는 정렬되어 있지만 블록 안은 정렬이 안된 상태에서 검색

4.해싱

• 데이터를 배치할 때 함수를 이용해서 배치하는 방식
• 모든 데이터의 검색 속도가 일정하고 가장 빠른 검색 방법
• 해싱 함수의 선택은 운영체제가 합니다.