Page 107 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

39는 원하는 키의 값과 일치하므로 검색 성공입니다.

이러한 n개의 요소가 오름차순으로 늘어선 배열 a에서 키를 이진 검색으로 검색하는 과정을
일반적인 방법으로 표현해 보겠습니다. 이때 검색 범위의 맨 앞 인덱스를 pl, 맨 끝 인덱스를
pr, 중앙 인덱스를 pc라고 지정합니다. 검색을 시작할 때 pl은 0, pr은 n – 1, pc는 (n – 1)/2로

초기화합니다. 여기까지 설명한 내용이 a 입니다.
검색 대상의 범위는 안의 요소이고 검색 대상에서 제외되는 범위는 안의 요
소입니다. 여기서 주목할 점은 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 (거의) 반으

로 좁혀진다는 것입니다. 또한 검사한 요소를 하나씩 제외시키는 선형 검색과는 다르게 이진
검색은 ●로 표시한 검색할 요소가 해당 단계에서 다음에 검색할 범위의 중간 지점으로 단숨
에 이동합니다.

검사할 요소(중앙 요소)
pl pc pr

여기에는 값이 존재하지 않음 검색 범위

pl pr
０ １ ２ ３ ４ ❺ ６ ７ ８ ９ １０
a 5 7 15 28 29 31 39 58 68 70 95

pl pr
０ １ ２ ３ ４ ５ ６ ７ ❽ ９ １０
b 5 7 15 28 29 31 39 58 68 70 95

pl pr
０ １ ２ ３ ４ ５ ❻ ７ ８ ９ １０
c 5 7 15 28 29 31 39 58 68 70 95
검색 성공!
검색할 값과 일치하는 요소를 발견
[그림 3-5] 이진 검색의 한 예(39를 검색 : 검색 성공)

c 처럼 a[pc]와 key를 비교하여 같으면 검색 성공입니다. 하지만 원하는 값을 찾지 못하면
아래와 같은 방법으로 검색 범위를 좁혀 갈 수 있습니다.

1. a[pc] < key일 때
a[pl] ~ a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외합니다. 검색 범위는 중앙

요소 a[pc]보다 뒤쪽의 a[pc + 1] ~ a[pr]로 좁혀집니다. 그런 다음 pl의 값을 pc + 1로 업데

03•검색 107