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

b 새로 검색할 범위에서 중앙 요소의 값은 15(a[2])입니다. 키 값인 6보다 크므로 검색할 범

위를 a[0] ~ a[1]로 좁힙니다.

c 새로 검색할 범위에서 중앙 요소의 값은 5(a[0])입니다. 키 값인 6보다 작으므로 pl을 pc +
1(1)로 업데이트합니다. 그러면 pl과 pr은 1이 됩니다.

d 축소된 범위의 중앙 요소의 값은 7(a[1])입니다. 키 값인 6보다 크므로 pr을 pc – 1(0)로 업
데이트합니다. 그러면 pl이 pr보다 커지면서 검색 범위를 더 이상 계산할 수 없게 됩니다. 종

료 조건 ②가 성립하므로 검색 실패입니다.

이 과정(이진 검색)을 구현한 프로그램이 실습 3-4입니다. 이진 검색은 검색을 반복할 때마다
검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n입니다. 검색에 실패한

경우는⎡log(n + 1)⎤회, 검색에 성공한 경우는 대략 log n – 1회입니다.

이진 검색 알고리즘은 검색 대상(배열)이 정렬(sort)되어 있음을 가정합니다. 따라서 이 프로그

램의 색칠된 부분은 사용자가 각 요소의 값을 입력하는 과정에서 바로 앞에 입력한 요소보다
작은 값인 경우에는 다시 입력하게 합니다. 위의⎡log(n + 1)⎤에 사용한 ⎡⎤는 천장 함수
(ceiling function)를 나타내는 기호입니다. 즉, ⎡x⎤는 x의 천장 함수이며, x보다 크거나 같으
면서 가장 작은 정수입니다. 예를 들어, ⎡3.5⎤는 4입니다. 천장 함수를 올림 함수라고도 합

니다.

실습 3-4 •완성 파일 chap03/bin_search.c
01 /* 이진 검색 */
실행 결과
02 #include <stdio.h>
이진 검색
03 #include <stdlib.h> 요소 개수 : 7
04 오름차순으로 입력하세요.
05 /*--- 요소의 개수가 n인 배열 a에서 key와 일치하는 요소를 이진 검색 ---*/ x[0] : 15
06 int bin_search(const int a[], int n, int key) x[1] : 27
07 { x[2] : 39
x[3] : 77
08 int pl = 0; /* 검색 범위 맨 앞의 인덱스 */
x[4] : 92
09 int pr = n - 1; /* 검색 범위 맨 끝의 인덱스 */ x[5] : 118
10 int pc; /* 검색 범위 한가운데의 인덱스 */ x[6] : 121
11 do { 검색값 : 39
12 pc = (pl + pr) / 2; 39는(은) x[2]에 있습니다.
13 if(a[pc] == key) /* 검색 성공 */

03•검색 109