탐색

1.Sequential search : Linear Search

2.Binary search(이진탐색) : 전체 데이터 순위 1/2씩 줄여가며 탐색을 진행, 정렬된 데이터를 기반
찾고자 하는 데이터의 범위를 절반씩 줄여가며 탐색을 수행
mid:(low + high) /2를 수행하여 중앙의 값과 찾고자 하는 데이터를 비교하여 데이터를 탐색하며, 찾고자 하는 값이 작으면 high= mid -1, 찾고자 하는 값이 크면 low= mid + 1을 수행하여 high 또는 mid 값을 변경한 후 mid값을 다시 계산해 가면서 탐색을 진행

예.) 10 20 30 40 50 60 70 80 90 100

3.fibonacci search : 정렬, 피보나치 수열의 값을 인덱스로 이용
0 1 1 2 3 5 8 13 21
. 34 ... 의 값을 인덱스로 사용 하여 탐색
전체 데이터 건수 보다 하나 더 큰 값을 Fk라고 정의하고, Fk-1, Fk-2 를 i, p, q 변수에 대입하여, 찾고자 하는 값과 배열의 a[i]를 비교하여 같으면 탐색종료, 찾고자 하는 값이 크면 i=i+q, p=p-q g=g-p를 수행하고 찾고자 하는 값이 작으면 i=i-q, t=p, p=q, g=t-q를 수행

4.Interpolatim search : 정렬

5.Block search : 블록 단위로 수의 범위가 정해져 있으며, 블록 내에서 순차 탐색을 수행