전화번호부에서 이름을 찾을 때 첫 장부터 한 줄씩 읽는 대신 가운데를 펼쳐 찾는 이름이 앞인지 뒤인지 판단하면 절반을 버릴 수 있습니다. 이진 탐색은 이 생각을 정렬된 배열에 적용한 알고리즘입니다. 한 번 비교할 때마다 후보 구간이 약 절반이 되므로 데이터가 크게 늘어도 비교 횟수는 천천히 증가합니다.
이진 탐색은 정렬된 배열의 탐색 구간을 반복해서 절반으로 줄이며, 시간복잡도는 O(log N)입니다.
반드시 정렬되어 있어야 하는 이유
오름차순 배열에서 가운데 값보다 찾는 값이 작다면 가운데 오른쪽에는 답이 없다고 확정할 수 있습니다. 값이 크다면 왼쪽을 버릴 수 있습니다. 배열이 정렬되지 않았다면 가운데 값 하나를 보고 어느 절반에 답이 없는지 알 수 없습니다. 따라서 정렬은 편리한 선택이 아니라 이진 탐색의 논리를 성립시키는 전제입니다.
한 번만 검색하려고 정렬되지 않은 자료를 먼저 정렬하면 일반적인 비교 정렬에 O(N log N)이 들고 탐색 자체보다 비용이 큽니다. 반대로 같은 자료에서 검색을 여러 번 한다면 한 번 정렬한 뒤 매 검색을 O(log N)에 처리하는 편이 유리할 수 있습니다. 자료의 갱신 빈도와 검색 횟수를 함께 봐야 합니다.
8개 값에서 찾는 과정을 따라가기
배열 [3, 8, 12, 17, 23, 31, 42, 57]에서 31을 찾는다고 하겠습니다. 인덱스 범위를 low=0, high=7로 두고 가운데 mid=3의 값 17을 확인합니다. 31이 더 크므로 0~3을 버리고 low=4로 바꿉니다. 새 가운데 mid=5의 값이 31이므로 두 번째 비교에서 검색이 끝납니다.
57을 찾으면 가운데 값 17, 31, 42, 57을 차례로 비교합니다. 첫 비교 뒤 후보는 4개, 다음은 2개, 다음은 1개로 줄어듭니다. 답이 없는 50을 찾는 경우에도 구간이 비면 종료하므로 모든 원소를 훑지 않습니다.
왜 로그 시간일까
처음 N개였던 후보가 k번 비교한 뒤 대략 N/2ᵏ개가 됩니다. 후보가 하나 이하가 되는 조건 N/2ᵏ≤1을 풀면 2ᵏ≥N이고 k≥log₂N입니다. 그래서 필요한 비교 횟수의 증가율이 log₂N에 비례합니다. 밑이 2인 것은 범위를 둘로 나누기 때문이지만 빅오 표기에서는 로그의 밑이 상수배 차이여서 O(log N)으로 씁니다.
| 원소 수 N | 최악의 성공 검색 비교 횟수 상한 |
|---|---|
| 8 | 4 |
| 1,024 | 11 |
| 1,048,576 | 21 |
| 약 10억 | 30 안팎 |
비어 있지 않은 배열에서 전형적인 구현의 최악 성공 검색 비교 횟수는 ⌊log₂N⌋+1 이하로 설명할 수 있습니다. 구현이 반열린 구간 [low, high)을 쓰는지 닫힌 구간 [low, high]를 쓰는지, 성공과 실패 중 무엇을 세는지에 따라 정확한 식은 조금 달라집니다. O(log N)은 이런 상수와 경계 차이를 제외한 증가율입니다.
안전한 가운데 인덱스 계산
가운데를 mid=(low+high)/2로 계산하면 고정 폭 정수에서 low+high가 최댓값을 넘어 오버플로할 수 있습니다. 두 인덱스가 각각 유효해도 합은 범위를 벗어날 수 있기 때문입니다. low와 high가 음수가 아닌 일반적인 배열 인덱스라면 mid=low+(high−low)/2로 같은 결과를 더 안전하게 계산합니다.
종료 조건과 한 칸 오류
닫힌 구간 방식에서는 low≤high인 동안 반복하고, 가운데 값이 작으면 low=mid+1, 크면 high=mid−1로 바꿉니다. mid를 그대로 남기면 원소가 두 개일 때 범위가 줄지 않아 무한 반복할 수 있습니다. 반열린 구간 방식은 high를 포함하지 않으므로 조건과 갱신식이 다릅니다. 두 방식을 섞는 것이 대표적인 오류입니다.
빈 배열, 원소 하나, 첫 원소, 마지막 원소, 없는 값, 같은 값이 반복된 배열을 시험하면 경계 오류를 빨리 찾을 수 있습니다. 이진 탐색은 아이디어보다 구간 불변식을 정확히 유지하는 구현이 중요합니다. 반복이 시작될 때마다 답이 있다면 반드시 현재 후보 구간 안에 있다는 명제를 유지해야 합니다.
중복 값에서는 어느 위치를 반환할까
같은 값이 여러 번 있으면 기본 이진 탐색은 그중 하나를 반환할 뿐 첫 번째나 마지막 위치를 보장하지 않습니다. 첫 위치가 필요하면 값이 같을 때도 왼쪽 절반을 계속 탐색하며 현재 위치를 후보로 저장합니다. lower_bound는 찾는 값 이상인 첫 위치, upper_bound는 찾는 값보다 큰 첫 위치를 구합니다. 두 위치의 차이는 정렬된 배열에서 해당 값의 개수입니다.
배열에서는 빠르지만 연결 리스트는 다르다
O(log N) 시간은 가운데 원소에 O(1)로 접근할 수 있는 정렬 배열을 전제로 합니다. 연결 리스트는 가운데 노드로 바로 갈 수 없어 포인터를 따라 이동해야 합니다. 비교 횟수는 로그 수준이어도 노드 이동을 합친 실행 시간은 O(N)이 될 수 있습니다. 자료구조의 접근 비용을 빼고 비교 횟수만 세면 실제 성능을 잘못 설명하게 됩니다.
탐색이 빠르다고 삽입도 빠른 것은 아니다
정렬 배열에서 새 값이 들어갈 위치는 이진 탐색으로 O(log N)에 찾을 수 있습니다. 하지만 그 자리를 만들기 위해 뒤쪽 원소를 한 칸씩 옮기면 삽입은 O(N)입니다. 균형 이진 탐색 트리는 검색과 삽입을 로그 시간에 지원할 수 있지만 메모리 배치와 균형 유지 비용이 따릅니다. 문제에 맞는 자료구조 선택이 필요합니다.
정답이 숫자 범위에 있을 때
이진 탐색은 배열 원소 찾기에만 쓰이지 않습니다. 어떤 값 x가 조건을 만족하면 그보다 큰 값도 모두 만족하는 단조 조건이 있으면 가능한 숫자 범위를 절반씩 줄일 수 있습니다. 예를 들어 제한 시간 안에 작업을 끝낼 수 있는 최소 속도, 예산 안에서 가능한 최대 규모를 찾는 문제입니다. 이를 흔히 매개변수 탐색 또는 정답에 대한 이진 탐색이라고 부릅니다.
페이지랭크와 비교해 보는 반복 계산
이진 탐색은 비교 결과로 후보 절반을 완전히 버리는 알고리즘입니다. 반면 구글 페이지랭크의 전이 행렬 반복 계산은 확률 벡터가 일정한 값에 가까워질 때까지 갱신합니다. 둘 다 반복할수록 답에 접근하지만, 하나는 정렬과 단조성을 이용한 구간 축소이고 다른 하나는 고유벡터로의 수렴이라는 차이가 있습니다.
핵심 점검 목록
- 자료가 탐색 기준에 따라 정렬되어 있는지 확인합니다.
- 닫힌 구간과 반열린 구간 중 하나를 정하고 종료 조건을 일관되게 씁니다.
- 가운데 인덱스는 low+(high−low)/2 형태로 계산합니다.
- 중복 값에서 임의 위치, 첫 위치, 마지막 위치 중 무엇이 필요한지 정합니다.
- 배열 접근, 정렬, 삽입 비용까지 포함해 전체 복잡도를 판단합니다.
선형 탐색과 실제 선택 기준
선형 탐색은 정렬이 필요 없고 앞에서부터 확인하므로 최악에 N번 비교합니다. 자료가 매우 작거나 답이 앞쪽에 자주 있고 한 번만 검색한다면 단순한 선형 탐색이 준비 비용과 구현 면에서 충분할 수 있습니다. 이진 탐색의 장점은 자료가 크고 정렬 상태를 유지하며 여러 번 검색할 때 뚜렷해집니다. 빅오만 보고 무조건 선택하기보다 캐시 접근, 비교 연산 비용, 정렬 유지 비용을 함께 측정해야 합니다.
불변식으로 구현을 검증하는 법
lower_bound를 찾는 반열린 구간 [low, high)에서는 low보다 앞의 값은 목표보다 작고, high 이후의 값은 목표 이상이라는 경계를 유지합니다. 가운데 값이 목표보다 작으면 low=mid+1, 아니면 high=mid로 줄입니다. 반복이 끝나 low=high가 되면 그 위치가 목표 이상인 첫 자리입니다. 매 단계에서 구간 길이가 반드시 감소하는지 확인하면 무한 반복과 누락을 동시에 막을 수 있습니다.
재귀 구현과 반복문 구현의 비교 횟수는 같은 차수입니다. 반복문은 호출 스택을 쓰지 않아 추가 공간을 O(1)로 유지하기 쉽고, 재귀형은 분할 구조를 직접 표현합니다. 어느 방식을 쓰든 구간 정의와 반환 규칙이 같다면 탐색 결과도 같아야 합니다.