이진 탐색(Binary Search): 업다운 게임으로 배우는 탐색의 기술

친구와 1부터 100까지의 숫자 중 하나를 맞히는 '업다운(Up & Down) 게임'을 한다고 상상해 보십시오. 무식하게 "1이야? 2야? 3이야?" 하고 하나씩 묻는 사람은 없을 것입니다. 가장 똑똑한 질문은 무조건 중간값인 "50이야?"부터 시작하는 것입니다. "업(Up)!"이라는 대답을 듣는 순간, 1부터 50까지의 숫자는 단 한 번의 질문으로 고려 대상에서 완전히 날아가 버리기 때문입니다. 데이터베이스의 거대한 인덱스 속에서 원하는 데이터를 빛의 속도로 꽂아내는 탐색 알고리즘의 꽃, '이진 탐색(Binary Search)'의 원리가 바로 이 게임에 있습니다.

1. 필수 전제 조건: "줄을 서시오" (정렬)

이진 탐색이 마법을 부리기 위해서는 절대적으로 지켜야 할 단 하나의 철칙이 있습니다. 바로 '데이터가 오름차순이나 내림차순으로 완벽하게 정렬(Sorted)되어 있어야 한다'는 것입니다. 데이터가 뒤죽박죽 섞여 있다면 "업"이나 "다운"이라는 힌트가 아무런 의미를 갖지 못하기 때문입니다. 정렬만 되어 있다면, 이진 탐색은 준비를 마친 것입니다.

2. 3개의 포인터: Low, High, Mid

이진 탐색은 탐색 범위를 관리하기 위해 세 개의 포인터를 운영합니다.

• Low: 탐색 범위의 맨 처음 인덱스
• High: 탐색 범위의 맨 끝 인덱스
• Mid: 탐색 범위의 정중앙 인덱스 (Low + High) / 2

2-1. 반의 반의 반으로 썰어버리기

우리가 찾는 타겟 숫자(Target)와 정중앙의 숫자(Mid)를 비교합니다.

1. Target == 배열[Mid]: 빙고! 한 번에 찾았습니다. 즉시 탐색을 종료합니다.
2. Target < 배열[Mid]: 타겟이 중앙값보다 작으므로, 중앙값의 오른쪽 절반은 이제 쓰레기통에 버려도 됩니다. 탐색 범위를 왼쪽으로 좁히기 위해 High = Mid - 1로 당겨옵니다.
3. Target > 배열[Mid]: 타겟이 중앙값보다 크므로, 왼쪽 절반을 버립니다. Low = Mid + 1로 밀어 올립니다.

이 과정을 Low <= High인 동안(탐색 범위가 1개로 쪼그라들 때까지) 끝없이 반복합니다.

3. O(log N)의 압도적인 파괴력

데이터가 100개일 때, 앞에서부터 하나씩 찾는 선형 탐색(Linear Search)은 최악의 경우 100번을 뒤져야 합니다. 하지만 이진 탐색은 한 번 질문할 때마다 남은 후보가 50개 → 25개 → 12개 → 6개 → 3개 → 1개로 반토막이 납니다. 단 7번 만에 답을 찾아냅니다.

만약 전 세계 인구인 80억 명의 주민등록번호가 정렬되어 있다면 어떨까요? 선형 탐색은 80억 번을 뒤져야 하지만, 이진 탐색은 반으로 써는 작업을 고작 33번만 반복하면 80억 명 중 정확히 당신을 찾아낼 수 있습니다. 데이터가 기하급수적으로 커질수록 탐색 횟수는 아주 천천히 늘어나는 O(log N)의 마법, 이것이 컴퓨터 시스템이 거대한 데이터베이스를 순식간에 검색해 내는 핵심 비결입니다.

[핵심 요약]
1. 이진 탐색(Binary Search)은 탐색 범위를 절반씩 좁혀나가며 원하는 데이터를 찾는 고속 검색 알고리즘으로, 반드시 데이터가 정렬되어 있어야만 사용 가능합니다.
2. 양 끝을 가리키는 Low, High 포인터의 중간값(Mid)을 타겟과 비교하여, 조건에 따라 절반의 데이터를 과감하게 버리는 로직을 반복합니다.
3. 탐색 범위가 매번 $\frac{1}{2}$로 줄어들므로 시간 복잡도는 O(log N)이 되며, 수십억 개의 데이터 속에서도 단 수십 번의 연산으로 정답을 핀포인트로 찾아냅니다.