제어 탐색

 

■ 제어 탐색(control Search)
    - 레코드의 키 값에 따라 오름차순 또는 내림차순으로 배열된 파일에서 탐색하려는 레코드의 키 값(K)과 비교되는 키 값(Ki)을 비교하여 K=Ki 이면 탐색이 성공한 경우, K>Ki 이면 Ki보다 뒤쪽에 찾고자 하는 레코드가 있고, K<Ki 이면 Ki보다 앞쪽에 찾고자 하는 레코드가 있다.
    - 비교되는 키 값을 선정하는 기준에 따라, 이진 탐색(binary search), 피보나치 탐색(fibonacci search), 보간 탐색(interpolation search) 등으로 구분한다.

■ 이진 탐색(binary search) ---> 이진 탐색 알고리즘
    - 중앙에 있는 레코드부터 조사하여 시작.
    - 주어진 키 값과 같으면 탐색이 된 것이고, 주어진 키 값보다 큰 경우는 뒤쪽을 탐색하고, 작으면 앞쪽을 탐색하면서 탐색 범위를 줄여나가는 방법.
    - 평균 탐색 길이 : log2(n+1)-1,    복잡도 : O(log2n)