🔭

[JS] Binary Search


이분 탐색?

이분 탐색은 결정 문제에서 사용할 수 있는 강력한 탐색 알고리즘이다. 결정 문제는 답이 true 혹은 false로 나오는 문제다.

이분 탐색의 아이디어는 경계를 포함하는 구간 leftright를 잡은 뒤 구간의 길이를 절반씩 줄여나가 leftright이 경계 지점에 위치하도록 하는 것이다. 구간을 절반씩 줄여나가야 하기 때문에 결정 문제는 주어진 대상을 두 구간으로 나눌 수 있어야 한다.

가장 유명한 사용 예시가 정렬된 배열에서 어떤 값을 찾는 것이다. arr = [1, 3, 6, 7, 9, 20]에서 9을 찾는다고 해보자. 이때 결정 문제를 'arr[index] >= 9인가?'로 잡으면 배열을 '9보다 작은 구간'과 '9보다 큰 구간'의 두 구간으로 나눌 수 있다. 이 결정 문제를 현재 구간의 중간에 적용하며 다음 구간을 찾으면 [0, 5], [2, 5], [3, 5], [3, 4]로 구간을 좁혀 원하던 숫자를 찾을 수 있다.

구현

먼저 결정 문제 check에 대해 check(left) !== check(right)가 되도록 left와 right를 설정한 뒤, left + 1 < right인 동안 check(left) === check(mid)라면 left = mid, 아니라면 right = mid를 해주면 된다.

이분 탐색이 끝나면 leftright은 답이 바뀌는 경계에 위치하게 된다. 만약 결정 문제에 대해 true인 것 중 가장 작은 것을 찾는다면 right가, 아니라면 left를 답으로 선택하면 된다.

1function binarySearch(arr, target) {
2 let left = 0, right = arr.length - 1;
3 while(left + 1 < right) {
4 const mid = Math.floor((left + right) / 2);
5 if(arr[mid] >= target) right = mid;
6 else left = mid;
7 }
8 return arr[right] === target ? right : -1;
9}

구간을 절반으로 줄여나가며 탐색하기 때문에 worst case에도 logN\log N번 탐색한다. 따라서 O(logN)O(\log N)의 시간 복잡도를 가진다. 10만개의 데이터가 있어도 약 16번 만에 탐색을 끝낼 수 있기 때문에 아주 강력하다.


참조:
https://www.acmicpc.net/blog/view/109
https://gyoogle.dev/blog/algorithm/Binary%20Search.html