이진탐색 - 반을 버릴 수 있을 때

두꺼운 국어사전에서 낱말을 찾을 때 아무도 1페이지부터 넘기지 않는다. 가운데를 펴고, 찾는 낱말이 앞이면 뒷장을 통째로 덮는다.

한 번 펴고 절반을 덮는다

사전에서 낱말을 찾는 동작을 그대로 옮기면 이진탐색이 된다.

가운데를 펴서 본다. 찾는 것이 그보다 뒤면 앞쪽 절반은 다시 볼 이유가 없다. 남은 절반에서 다시 가운데를 편다. 반복하면 남은 범위가 반씩 줄어든다.

100만 개에서 시작해도 스무 번이면 하나가 남는다. 훑으면 100만 번인 일이 스무 번이 된다. 놀라운 건 데이터가 두 배가 되어도 딱 한 번만 더 편다는 것이다.

절반을 버릴 수 있는 조건

이 방법이 성립하려면 하나가 필요하다. 한 곳을 봤을 때 답이 어느 쪽에 있는지 알 수 있어야 한다.

정렬이 그 조건을 만들어 준다. 줄이 서 있으면 가운데 값 하나만 보고도 “찾는 건 왼쪽” 또는 “오른쪽”이 확정된다. 줄이 안 서 있으면 가운데를 봐도 아무것도 안 걸러진다.

⚠️ 정렬되지 않은 배열에 이진탐색을 걸면 에러가 나지 않는다. 그냥 “없다”고 답하거나 엉뚱한 자리를 준다. 있는 값을 못 찾고 넘어가는데 아무도 안 알려주는 게 이 함정의 고약한 점이다.

그리고 조건은 “정렬”보다 조금 넓다. 진짜 조건은 어느 지점을 기준으로 답이 한쪽에만 있다는 성질이다. 예를 들어 [거짓, 거짓, 거짓, 참, 참, 참]처럼 한 번 바뀌면 되돌아오지 않는 배열이라면, 값이 정렬되어 있지 않아도 참이 처음 나오는 자리를 이진탐색으로 찾을 수 있다.

짧은데 자주 틀린다

이진탐색은 열 줄이 안 되는데 정확히 짜는 사람이 드문 것으로 유명하다. 틀리는 자리가 정해져 있다.

int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;      // (lo + hi) / 2는 값이 크면 넘친다
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) lo = mid + 1;   // +1이 없으면 무한 루프
    else hi = mid - 1;                     // -1이 없으면 무한 루프
}
return -1;

주석 세 줄이 전부 실제로 밟히는 자리다.

가운데를 구하는 줄이 넘친다. lo + hi가 정수 범위를 넘으면 음수가 되고, 배열 접근이 터진다. 배열이 10억 개를 넘어야 나타나서 평소엔 멀쩡하다. 자바 표준 라이브러리의 이진탐색에도 이 버그가 있었고, 여러 해 동안 아무도 못 찾았다.

범위를 줄일 때 1을 안 빼면 안 끝난다. hi = mid로 두면 후보가 둘 남았을 때 mid가 계속 같은 자리를 가리켜서 영원히 돈다. 알고리즘의 첫 조건이 “반드시 끝난다”였는데, 그 조건이 여기서 깨진다.

등호 하나로 답이 달라진다. while (lo <= hi)와 while (lo < hi)는 마지막 한 칸을 검사하느냐 마느냐를 가르고, 그래서 “없는 값을 찾을 때”의 결과가 달라진다.

그래서 실무 조언은 분명하다. 직접 짜지 말고 라이브러리를 쓴다. 그럼에도 원리를 아는 이유는 다음 절에 있다.

있는지가 아니라 어디까지인지를 묻는다

실무에서 이진탐색이 정말 값을 하는 자리는 “이 값이 있나”가 아니다. 경계를 찾는 것이다.

• 정렬된 로그에서 특정 시각 이후 첫 항목은 어디부터인가
• 점수 목록에서 80점 이상이 몇 명인가
• 정렬된 목록에서 이 값을 넣을 자리는 몇 번째인가

셋 다 “찾는 값이 없을 수도 있는” 질문이고, 답은 자리 번호다. 라이브러리들이 이런 이름을 따로 두는 이유가 여기 있다. 자바의 Arrays.binarySearch는 없는 값이면 들어갈 자리를 음수로 인코딩해서 돌려주고, 파이썬은 bisect_left와 bisect_right로 같은 값이 여럿일 때 앞이냐 뒤냐까지 나눈다.

“있나 없나”만 쓰고 나머지를 안 쓰면 이진탐색의 절반을 안 쓰는 것이다.

정렬이라는 입장료

이진탐색은 정렬을 전제로 하는데, 정렬 자체가 n log n이다. 한 번 찾자고 정렬하는 건 손해다. 그냥 한 바퀴 훑으면 n이다.

갈리는 지점은 몇 번 찾느냐다.

• 한두 번 찾고 만다면 정렬하지 말고 훑는다.
• 같은 데이터를 계속 찾는다면 한 번 정렬해 두고 매번 스무 번에 끝낸다.
• 자주 바뀌면서 자주 찾는다면 정렬 상태를 유지하는 비용이 계속 든다. 이때는 순서를 지키면서 넣고 빼는 그릇이나 해시테이블 쪽이 맞다.

이 판단은 자료구조를 고를 때 했던 것과 같은 판단이다. 한 번 치르는 값이냐, 매번 치르는 값이냐.

답 자체를 반씩 좁히기도 한다

한 걸음 더 나간 쓰임이 있다. 배열이 아니라 답의 범위를 이진탐색하는 것이다.

“밧줄 여러 개를 잘라 같은 길이로 K개를 만들 때, 가능한 최대 길이는?” 같은 문제가 그렇다. 길이를 하나 정해놓고 “이 길이로 K개가 나오나”는 쉽게 확인된다. 그리고 이 확인은 길이가 짧을수록 참, 길수록 거짓이라 한 번 바뀌면 되돌아오지 않는다.

그러면 답 후보 구간을 반씩 좁힐 수 있다. 가능한지 확인하는 함수만 있으면 답을 이진탐색으로 찾는다. 이 꼴이 보이면 대개 “최대의 최소” 또는 “최소의 최대”라는 말이 문제에 들어 있다.

실무에서: 이진탐색은 대개 인덱스라는 이름으로 온다

애플리케이션 코드에 이진탐색을 손으로 적는 일은 드물다. 대신 이미 이진탐색으로 돌아가는 것을 쓰고 있다.

인덱스가 왜 빠른가의 답이 이거다. 인덱스는 정렬된 구조라서 DB가 값을 찾을 때 처음부터 훑지 않고 범위를 반씩 좁힌다. 그래서 이 글의 조건들이 그대로 인덱스의 성질이 된다.

• 인덱스는 정렬을 유지해야 해서 쓰기가 비싸다. 이진탐색의 입장료를 매 삽입마다 나눠 내는 것이다.
• 인덱스가 있으면 범위 조회가 싸다. 경계를 찾는 일이 이진탐색이고, 거기서부터 순서대로 읽으면 끝이다.
• 인덱스 컬럼에 함수를 씌우면 인덱스를 못 쓴다. 정렬 순서가 깨져서 “답이 어느 쪽인지” 판단이 성립하지 않기 때문이다.

마지막 줄이 실무에서 제일 자주 밟는다. WHERE DATE(created_at) = '2025-09-15'는 인덱스를 못 쓰고, WHERE created_at >= '2025-09-15' AND created_at < '2025-09-16'는 쓴다. 같은 뜻인데 반을 버릴 수 있느냐가 갈린다.

정리

• 이진탐색은 한 번 보고 절반을 버리는 것이다. 100만 개가 스무 번이 된다.
• 성립 조건은 정렬이 아니라 더 넓다. 한 곳을 보고 답이 어느 쪽인지 알 수 있으면 된다.
• 짧은데 자주 틀린다. 가운데 계산의 넘침, 범위를 줄일 때의 1, 등호 하나. 직접 짜지 말 것.
• 실무의 쓰임은 “있나”보다 **“어디부터인가”**다. 경계를 찾는 도구로 써야 값을 한다.
• 정렬은 입장료다. 몇 번 찾을 것인가가 정렬할지 말지를 정한다.
• DB 인덱스가 이진탐색이다. 컬럼에 함수를 씌우면 반을 버릴 수 없게 되어 인덱스가 죽는다.

다음 글은 지금까지 슬쩍 지나간 도구를 정면으로 본다. 자기를 부르는 함수, 재귀다.