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

이트합니다( a ⇨ b ).

2. a[pc] > key일 때
a[pc] ~ a[pr]은 key보다 큰 것이 분명하므로 검색 대상에서 제외합니다. 검색 범위는 중앙
요소 a[pc]보다 앞쪽 a[pl] ~ a[pc – 1]로 좁혀집니다. 그런 다음 pr의 값을 pc – 1로 업데이트

합니다( b ⇨ c ).

이진 검색 알고리즘의 종료 조건은 아래 조건 ①, ② 중 하나만 성립하면 됩니다.

① a[pc]와 key가 일치하는 경우
② 검색 범위가 더 이상 없는 경우

그림 3-5는 조건 ①이 성립하여 검색에 성공한 예입니다. 그러면 조건 ②가 성립하여 검색에

실패하는 구체적인 예도 생각해 보겠습니다. 같은 배열에서 6을 검색하는 과정을 그림 3-6에
나타냈습니다.

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

pl pr
０ ❶ ２ ３ ４ ５ ６ ７ ８ ９ １０
d 5 7 15 28 29 31 39 58 68 70 95
pr pl
０ １ ２ ３ ４ ５ ６ ７ ８ ９ １０
e 5 7 15 28 29 31 39 58 68 70 95
검색 실패!
검색 범위가 더 이상 없습니다.
[그림 3-6] 이진 검색의 한 예(6을 검색 : 검색 실패)

a 검색할 범위는 모든 배열(a[0] ~ a[10])이고 중앙 요소 a[5]의 값은 31입니다. 키 값인 6보다

크므로 검색 범위를 a[0] ~ a[4]로 좁힙니다.

108 C 알고리즘