이진 검색이란?
이진 검색(binary search)은 '반구간 검색(half-interval search)', '로그 검색(logarithmic search)', 또는 'binary chop'이라고도 불리는 탐색 알고리즘으로, 정렬된 배열 안에서 특정 목표값의 위치를 찾아냅니다. 이진 검색은 목표값을 배열의 중간 요소와 비교하는 방식으로 동작합니다. 두 값이 같지 않다면 목표값이 존재할 수 없는 절반을 제거하고, 남은 절반에서 다시 중간 요소와 비교하는 과정을 목표값을 찾을 때까지 반복합니다. 만약 탐색 범위가 완전히 비어 있게 되면, 배열에 목표값이 존재하지 않는다는 것을 의미합니다.
개념 자체는 매우 단순하지만, 이진 검색을 정확하게 구현하려면 종료 조건과 중간 지점(midpoint) 계산과 관련된 세부 사항에 주의해야 합니다. 특히 배열의 값들이 해당 범위의 모든 정수를 포함하지 않는 경우에는 더욱 신중한 처리가 필요합니다.
이진 검색의 효율성
이진 검색은 가장 널리 사용되는 탐색 알고리즘 중 하나로, 뛰어난 효율성 덕분에 다양한 문제 해결에 활용되는 대표적인 기법입니다.
예를 들어, 세상의 모든 이름을 사전순으로 나열한 뒤 특정 이름의 위치를 찾는다고 가정해 보겠습니다. 이진 검색을 사용하면 단 최대 35번의 반복만으로 원하는 이름을 찾아낼 수 있습니다.
이진 검색의 전제 조건
이진 검색은 반드시 정렬된 데이터 집합에서만 동작합니다. 따라서 컬렉션에 이진 검색을 적용하려면 먼저 해당 컬렉션을 정렬해야 합니다.
정렬된 집합에 이진 검색을 적용하면, 찾고자 하는 값을 기준으로 탐색 범위를 절반씩 줄여 나가므로 반복 횟수를 항상 크게 줄일 수 있습니다.
동작 과정 예시
다음 배열을 살펴보겠습니다.
선형 검색(linear search)을 사용할 경우, 요소 8의 위치를 찾기 위해 무려 9번의 반복이 필요합니다.
이번에는 이진 검색을 활용해 반복 횟수를 어떻게 줄일 수 있는지 살펴보겠습니다. 탐색을 시작하기 전에 먼저 탐색 범위의 시작점과 끝점을 알아야 합니다. 각각 Low(하한)와 High(상한)라고 부르겠습니다.
Low = 0
High = n-1
그다음, 찾고자 하는 값 K를 하한과 상한의 중간 위치에 있는 요소와 비교합니다. K가 더 크면 하한을 올리고, 그렇지 않으면 상한을 내립니다.
위 이미지에서 하한은 0, 상한은 9입니다.
하한과 상한의 중간값은 (lower_bound + upper_bound) / 2 = 4이며, 이때 a[4] = 4입니다. 찾고자 하는 값은 2인데, a[4] = 4 > 2이므로 인덱스 4 이후의 요소들은 당연히 2보다 큽니다. 따라서 그 이후의 요소들을 탐색할 필요가 전혀 없습니다.
따라서 상한을 요소 4의 위치로 낮출 수 있습니다. 이제 같은 배열에 대해 다음 값들로 동일한 절차를 반복합니다.
Low: 0
High: 3
이 절차를 Low > High가 될 때까지 재귀적으로 반복합니다. 어느 시점에서 a[mid] = key를 만족하면 mid 값을 반환하는데, 이것이 바로 key가 배열에 위치한 인덱스입니다. 만약 key가 배열에 존재하지 않으면 -1을 반환합니다.
C++ 구현 예제
int binarySearch(int low,int high,int key){
while(low<=high){
int mid=(low+high)/2;
if(a[mid]<key){
low=mid+1;
}
else if(a[mid]>key){
high=mid-1;
}
else{
return mid;
}
}
return -1; //key not found
}