이진 탐색은 업다운 게임의 필승 전략
크리스가 친구와 "업다운(Up-Down) 게임"을 하고 있다.
1부터 100까지의 숫자 중 친구가 생각한 숫자를 맞히는 게임이다.
크리스: "1?"
친구: "Up."
크리스: "2?"
친구: "Up."
크리스: "3?"
친구: "..."
친구가 화를 냈다. "너 100까지 다 부를 셈이야?"
이것이 지난 시간에 배운 선형 탐색(Linear Search)이다. 100번을 다 물어봐야 할 수도 있다.
똑똑한 크리스라면 이렇게 물었을 것이다.
크리스: "50!"
친구: "Down." (이제 51~100은 생각할 필요도 없다. 범위가 절반으로 줄었다!)
크리스: "25!"
친구: "Up." (1~24도 버린다.)
단 두 번의 질문으로 후보를 100개에서 25개로 줄였다. 이것이 바로 이진 탐색(Binary Search)의 마법이다.
1. 반으로 쪼개서 버린다 (Divide and Conquer)
이진 탐색은 "정렬된 데이터"에서만 사용할 수 있는 아주 강력한 알고리즘이다.
핵심은 탐색 범위를 절반씩 줄여나가는 것이다.
2. 자바스크립트로 구현하기
이진 탐색을 구현하려면 3개의 포인터(변수)가 필요하다.
function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;
// 왼쪽 포인터가 오른쪽 포인터를 넘어가면 탐색 종료 (못 찾음)
while (left <= right) {
// 중간 인덱스 계산
let mid = Math.floor((left + right) / 2);
let currentElement = arr[mid];
// 1. 찾았다!
if (currentElement === target) {
return mid;
}
// 2. 찾는 값이 더 작다면? -> 오른쪽(큰 쪽)을 버림
if (target < currentElement) {
right = mid - 1;
}
// 3. 찾는 값이 더 크다면? -> 왼쪽(작은 쪽)을 버림
else {
left = mid + 1;
}
}
return -1; // 끝내 못 찾음
}
// 주의: 반드시 정렬된 배열이어야 함!
const sortedStates = ["Alabama", "Alaska", "Arizona", "Arkansas", "California", ...];
binarySearch(sortedStates, "California");3. 성능 분석: 로그(log)의 위력
이진 탐색의 시간 복잡도는 O(log N)이다.
이게 얼마나 빠른 걸까?
선형 탐색이 40억 번 질문할 때, 이진 탐색은 32번만 질문하면 된다. 압도적인 차이다.
4. 치명적인 제약 조건: 정렬
"와, 그럼 무조건 이진 탐색만 쓰면 되겠네요?"
아쉽게도 전제 조건이 있다. 데이터가 반드시 순서대로 정렬되어 있어야 한다.
따라서 우리가 2장에서 배운 정렬(Sorting)이 여기서 빛을 발하는 것이다.
데이터를 한 번 정렬해두는 비용(O(N log N))을 투자하면, 이후의 검색을 O(log N)으로 평생 꿀 빨 수 있다.
5. 핵심 정리
이제 일직선으로 된 데이터(배열)를 검색하는 법은 마스터했다.
하지만 세상의 모든 데이터가 한 줄로 서 있지는 않다.
폴더 구조, 조직도, HTML DOM 트리... 이렇게 가지치기(Tree/Graph) 형태로 뻗어 나가는 데이터는 어떻게 탐색해야 할까?
미로 찾기 게임처럼 갈림길을 탐험하는 두 가지 방법, DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)를 배울 차례다.