[Algorithm]이진탐색(Binary Search)

이진탐색(Binary Search)

정렬된 상태의 입력 데이터에 대한 효과적인 탐색 방법

오름차순

탐색 방법

배열의 가운데 원소 A[x]와 탐색키 y를 비교.

1) 탐색키 = 가운데 원소 -> 탐색 성공(인덱스 x)를 반환 후 종료
2) 탐색키 < 가운데 원소 -> '이진 탐색(원래 크기 1/2인 왼쪽 부분 배열) ': 순환호출
3) 탐색키 < 가운데 원소 -> '이진 탐색(원래 크기 1/2인 오른쪽 부분 배열) ': 순환호출

예제

T(n) = T(n/2) + O(1) (n > 1), T(1) = 1

T(n) = O(logn)

특징

• 배열의 데이터가 정렬된 경우에만 적용.

• 삽입 / 삭제 연산은 부가적인 데이터 이동을 수반.

  데이터의 정렬 상태 유지를 위해서 평균 n/2개의 데이터 이동이 발생.

  -> 삽입 / 삭제가 빈번한 응용에서는 부적합.