이진 탐색 (Binary Search Algorithm)

 

 

 

 

검색 범위를 줄여나가면서, 원하는 데이터를 찾는 전체 탐색 알고리즘이다.

시간복잡도는 \( log{2}^{N} \) 으로 매우 빠르다.

단점으로는 이미 정렬된 자료에 대해서만 사용할 수 있다.

 

예시) 16을 찾아보자.

 

1단계

left index: 0

right index: 14

mid index: (0 + 14) / 2 = 7

A[mid] 값이 찾고자 하는 값(17)보다 큰 지 작은지 확인한다. · · · · · · · · · · ①

① 결과에 따라 검색 범위를 조정한다.

만약 A[mid] 값이 찾고자 하는 값 보다 크다면,  찾고자 하는 값이 mid 보다 왼쪽에 있으므로,

right 값을 수정한다. (right = mid - 1)

만약 A[mid] 값이 찾고자 하는 값 보다 작다면, 찾고자 하는 값이 mid 보다 오른쪽에 있으므로,

left 값을 수정한다. (left = mid + 1)

 

2단계

left index: 0

right index: 6

mid index: (0 + 6) / 2 = 3

 

3단계

left index: 4

right index: 6

mid index: (4 + 6) / 2 = 5

 

4단계 (찾음)

left index: 6

right index: 6

mid index: (6 + 6) / 2 = 6

 

 

만약 검색 구간이 (left > right) 이면,

데이터를 찾지 못한 것이다. (검색 종료)