DAA-이진 검색

이 장에서는 나누기 및 정복 방법을 기반으로하는 또 다른 알고리즘에 대해 설명합니다.

문제 설명

이진 검색은 정렬 된 배열에서 수행 할 수 있습니다. 이 접근 방식에서 요소의 색인은x요소가 요소 목록에 속하는지 결정됩니다. 배열이 정렬되지 않은 경우 선형 검색을 사용하여 위치를 결정합니다.

해결책

이 알고리즘에서 우리는 요소가 x 배열에 저장된 일련의 숫자에 속합니다. numbers[]. 어디l 과 r 검색 작업을 수행해야하는 하위 배열의 왼쪽 및 오른쪽 인덱스를 나타냅니다.

Algorithm: Binary-Search(numbers[], x, l, r)
if l = r then  
   return l  
else 
   m := ⌊(l + r) / 2⌋ 
   if x ≤ numbers[m]  then 
      return Binary-Search(numbers[], x, l, m) 
   else 
      return Binary-Search(numbers[], x, m+1, r)

분석

선형 검색 실행 O(n)시각. 이진 검색은 결과를 생성하는 반면O(log n) 시각

허락하다 T(n) 배열에서 최악의 경우 비교 횟수 n 집단.

그 후,

$$ T (n) = \ begin {cases} 0 및 if \ : n = 1 \\ T (\ frac {n} {2}) + 1 및 그렇지 않으면 \ end {cases} $$

이 반복 관계 사용 $ T (n) = log \ : n $.

따라서 이진 검색은 $ O (log \ : n) $ 시간을 사용합니다.

예

이 예에서는 요소 63을 검색합니다.