Page 106 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)
P. 106
03-3 이진 검색
이 절에서는 이진 검색법에 대해 살펴보겠습니다. 이 알고리즘을 적용하는 전제 조건은 데이
터가 키 값으로 이미 정렬(sort)되어 있다는 것입니다. 이진 검색은 선형 검색보다 좀 더 빠르
게 검색할 수 있다는 장점이 있습니다.
이진 검색
이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알
고리즘입니다. 정렬 알고리즘은 6장에서 살펴봅니다.
아래 그림에서 오름차순으로 정렬된 데이터에서 39를 검색하는 과정을 생각해 보겠습니다.
먼저 배열의 중앙에 위치한 요소인 a[5](31)부터 검색을 시작합니다.
０ １ ２ ３ ４ ❺ ６ ７ ８ ９ １０
5 7 15 28 29 31 39 58 68 70 95
검색하려는 값인 39는 중앙 요소(a[5])보다 큰 값입니다(뒤쪽에 존재). 그러므로 검색 대상을 뒤
쪽의 5개(a[6] ~ a[10])로 좁힐 수 있습니다. 그런 다음 검색 범위의 중앙에 위치한 요소인 a[8]
(68)이 원하는 값인지 확인합니다.
０ １ ２ ３ ４ ５ ６ ７ ❽ ９ １０
5 7 15 28 29 31 39 58 68 70 95
검색하려는 값인 39보다 큰 값입니다(앞쪽에 존재). 그러므로 검색 대상을 앞쪽의 2개(a[6] ~
a[7])로 좁힐 수 있습니다. 이제 검색해야 하는 대상은 2개입니다. 이때 두 요소의 중앙 요소는
39나 58 중 아무거나 선택해도 상관없지만 여기서는 앞쪽의 값 39를 선택하여 원하는 값인
지 확인합니다.
두 인덱스 6과 7의 중앙값은(6 + 7) / 2로 계산하여 6이 되기 때문입니다. 정수의 나눗셈은 나머지를 버립니다.
０ １ ２ ３ ４ ５ ❻ ７ ８ ９ １０
5 7 15 28 29 31 39 58 68 70 95
106 C 알고리즘
