이분 탐색 언제 쓰나, bisect·lower_bound 판단표와 경계 버그 체크리스트

정렬된 배열에서 값을 찾는 일은 이분 탐색 한 줄이면 되지만, 실무에서 막히는 곳은 알고리즘이 아니라 "이 상황에 이분 탐색이 맞나"와 "어느 함수를 불러야 하나" 예요. 결론부터 말하면 값이 있는지만 물을 때는 해시(set·HashSet)가 이기고, 이분 탐색은 "x 이상 첫 위치", "이 구간에 몇 개", "가장 가까운 값" 처럼 순서가 필요한 질문에서, 데이터가 거의 안 바뀔 때 가장 싸요. 자주 바뀌면 정렬 배열 유지 비용이 원소 수에 비례해 커져서 다른 구조로 가야 해요.

경계를 찾는 원리 자체는 안다고 보고, 이 글은 고를 때와 고칠 때 필요한 숫자만 다뤄요. 아래 측정은 Apple M1 에서 파이썬 3.13.7 과 OpenJDK 24.0.2 로 직접 돌린 값이에요. 절대 시간은 기기와 부하에 따라 달라지니 배수와 증가 모양으로 읽어 주세요.

이분 탐색이 맞는 질문, 질문별 함수 판단표

이분 탐색이 해시보다 나은 경우는 순서가 답에 들어가는 질문이에요. 해시는 "같은 키"만 찾을 수 있어서 "10시 이후 첫 로그", "5만~10만 원 사이 주문 수" 같은 질문에는 전체를 훑어야 해요. 정렬 배열이면 경계 두 번 찾고 빼면 끝이에요.

질문마다 불러야 할 함수가 달라요. 같은 값이 여럿일 때 결과가 달라지는 함수가 섞여 있어서, 표의 "중복 처리" 칸을 꼭 보세요.

몇 가지는 문서에 적힌 동작을 꼭 확인해야 해요.

• Go slices 패키지 문서는 slices.BinarySearch 가 같은 값 중 가장 앞 위치를 돌려준다고 적어요. 반면 자바 Arrays 문서의 binarySearch 는 같은 값이 여럿이면 어느 것이 나올지 보장하지 않아요. 이름이 비슷해도 쓰임이 달라요.
• 러스트 slice 문서도 binary_search 는 여러 일치 중 아무거나 돌려줄 수 있다며, 범위가 필요하면 partition_point 를 쓰라고 예제를 보여 줘요.
• 자바 subSet(...).size() 는 뷰를 하나씩 세어서 개수에 비례하는 시간이 들어요. 개수만 자주 필요하면 정렬 배열 두 번 탐색이 훨씬 싸요.

이분 탐색 vs 해시 vs 선형 탐색, 조회 시간과 메모리 비교

정렬된 정수 리스트에서 무작위 값 1만 개를 찾는 시간을 크기별로 쟀어요. 값이 있을 확률은 10%이고, 리스트 컴프리헨션 자체 시간은 빼서 조회 한 번 비용만 남겼어요.

1. 있는지만 물으면 해시가 압도적이에요. 크기와 상관없이 수십~100ns 대였고, 100만 건에서 bisect 보다 34배 빨랐어요.
2. 아주 작은 목록은 그냥 훑어도 돼요. 리스트 in 은 4건 147ns, 16건 364ns, 64건 1,270ns, 256건 7,531ns 였어요. 4건에서는 bisect(197ns)보다 빨랐고 16건부터 역전됐어요. 원소 10개 안팎의 설정 테이블에 이분 탐색을 짜 넣을 이유는 없어요.
3. 이분 탐색 비용은 비교 횟수보다 메모리 접근이 정해요. 100만 건은 비교 20번인데 4µs 가 넘었어요. 비교 한 번에 200ns 꼴로, 파이썬 리스트가 정수를 포인터로 들고 있어 매번 다른 메모리를 읽기 때문이에요.

메모리는 반대예요. 100만 개 정수를 담은 리스트 본체는 8.0MB, 같은 값을 담은 set 본체는 33.6MB 였어요(정수 객체 32MB 는 둘이 같이 써요). 자바는 차이가 더 커요. int[] 100만 칸은 4MB 인데, 같은 값을 TreeSet<Integer> 에 넣으니 약 56MB, HashSet<Integer> 은 약 57MB 가 늘었어요(System.gc() 후 사용량 차이로 잰 근삿값). 조회는 Arrays.binarySearch 약 440ns, TreeSet.ceiling 약 2,100ns, HashSet.contains 약 200ns 였어요.

읽기만 하는 큰 데이터라면 정렬 배열이 메모리로 14배 이상 싸요.

정렬 배열 유지 비용, 수정이 잦으면 계산부터

정렬 배열의 약점은 수정이에요. 파이썬 bisect 문서도 insort 는 탐색이 O(log n) 이지만 느린 O(n) 삽입 단계가 지배한다고 적어요. 가운데에 하나 넣으려면 뒤쪽 원소를 전부 한 칸씩 밀어야 하기 때문이에요. 크기를 유지하며 무작위 위치에 넣고 빼기를 2,000번씩 반복해 한 번 평균을 냈어요.

이 숫자로 감당 가능한 수정 빈도를 바로 계산할 수 있어요. 100만 건이면 한 번에 1.3ms 라 한 코어로 초당 약 770번이 한계이고, 그동안 다른 일은 못 해요. 10만 건이면 초당 약 7,000번이에요. 이보다 자주 바뀌면 이렇게 골라요.

• 모았다가 한 번에 정렬: 수정이 몰려 오고 읽기는 가끔이면 extend() 후 sort() 한 번이 가장 싸요. 이미 정렬된 부분이 많으면 정렬이 거의 한 번 훑는 비용이라서예요. 배수는 파이썬·자바 정렬 성능 판단표에 재 둔 값이 있어요.
• 자바 TreeMap·TreeSet: TreeMap 문서가 넣기·빼기·찾기를 log(n) 으로 보장해요. 위 측정처럼 메모리는 10배 넘게 들지만 수정 비용이 크기에 비례하지 않아요. floorKey·ceilingKey·subMap 이 이분 탐색 질문을 그대로 대신해요.
• DB 인덱스: 여러 서버가 같이 쓰거나 재시작 뒤에도 남아야 하면, B-트리 인덱스에 WHERE ts >= ? AND ts < ? 로 묻는 게 같은 일을 해요. 앱 메모리에 사본을 두는 건 읽기 전용 캐시일 때만이에요.

자바 Collections.binarySearch 에 LinkedList 를 넘기는 것도 피해요. Collections 문서는 RandomAccess 가 아닌 큰 리스트에서는 비교는 O(log n) 이어도 링크를 따라가는 이동이 O(n) 이라고 적어요. OpenJDK 소스의 기준 크기(BINARYSEARCH_THRESHOLD)는 5,000이에요.

반복 횟수 계산, 이분 탐색이 몇 번 도나

이분 탐색 한 번의 비교 횟수는 원소 n 개일 때 최대 ⌈log₂(n+1)⌉ 이에요. 직접 계산한 값이에요.

배열 탐색은 비교 한 번이 싸서 이 숫자가 문제 될 일이 드물어요. 무거운 건 파라메트릭 서치예요. "답이 L 이하로 가능한가"를 판정하는 함수가 매번 데이터 전체를 훑으면, 전체 비용은 판정 비용 × ⌈log₂(범위 크기)⌉ 예요.

예로 1~10,000 사이 정수 10만 개를 연속 구간 50개 이하로 나눠 구간 합 최댓값을 최소로 만드는 문제를 풀어 봤어요. 판정 한 번(탐욕으로 나눠 보기)이 파이썬에서 약 24ms 였어요.

S, M, k = sum(nums), max(nums), 50
# 넓은 범위: 가장 큰 원소 ~ 전체 합
lo, hi = M, S                         # 범위 약 5억 → 판정 29번
# 좁힌 범위: 평균 몫 ~ 평균 몫 + 가장 큰 원소
lo, hi = max(M, -(-S // k)), -(-S // k) + M   # 범위 1만 → 판정 14번

좁힌 상한이 성립하는 이유는 간단해요. 한도를 "평균 몫 + 가장 큰 원소"로 잡으면 탐욕으로 닫힌 구간마다 합이 평균 몫을 넘으니, 구간이 k 개를 넘을 수 없어요. 이렇게 범위 양끝을 문제에서 증명할 수 있는 값으로 잡으면 판정 횟수가 절반으로 줄어요. 판정이 DB 조회나 시뮬레이션처럼 무거우면 이 차이가 그대로 비용이에요.

실수 이분 탐색, 오차로 멈추면 무한 루프

값이 실수인 파라메트릭 서치에서 while hi - lo > 1e-9: 로 멈추는 코드가 흔해요. 이 조건은 값의 크기가 크면 영원히 참이에요. 배정밀도 실수는 1 근처에서 간격이 약 2.2×10⁻¹⁶ 이지만, 100만 근처에서는 약 1.16×10⁻¹⁰, 10억 근처에서는 약 1.19×10⁻⁷ 이에요(파이썬 math.ulp 로 확인). 10억 근처에서 lo 와 hi 가 이웃한 두 실수가 돼도 차이가 1.19×10⁻⁷ 이라 1e-9 보다 작아질 수 없어요. 실제로 1만 번 돌려도 끝나지 않았어요.

반대로 0 근처를 향해 줄이면 비정규 수까지 내려가서, mid 가 더는 안 바뀔 때까지 1,074번을 돌았어요. 그래서 멈추는 조건은 이렇게 잡아요.

• 반복 횟수로 멈추기: 범위 R 을 오차 ε 까지 줄이는 데 필요한 횟수는 ⌈log₂(R/ε)⌉ 이에요. 0~10억을 10⁻⁶ 까지 줄여도 50번이라, 넉넉히 100번 고정이면 충분해요.
• 상대 오차로 멈추기: hi - lo <= eps * max(1, abs(lo)) 처럼 값 크기에 비례한 기준을 써요.
• 정수로 바꾸기: 금액·시간처럼 최소 단위가 있으면 원·밀리초 정수로 바꿔 정수 이분 탐색을 해요. 경계가 깔끔하고 반복 횟수도 정해져요.

오버플로가 실제로 나는 곳, 배열보다 값 범위

(lo + hi) / 2 오버플로는 조슈아 블로크의 2006년 글로 유명해졌지만, 배열 인덱스에서 이 버그를 만나려면 생각보다 큰 배열이 필요해요. 32비트 int 에서 lo + hi 가 2³¹ - 1 을 넘으려면 hi 가 약 2³⁰(약 10.7억)을 넘어야 하고, 그런 int[] 는 4GiB 예요.

실무에서 더 자주 터지는 곳은 값 범위를 찾는 파라메트릭 서치예요. 답 후보가 0~20억이면 첫 반복부터 넘쳐요. 언어별로 이렇게 나와요.

자바스크립트는 숫자가 64비트 실수라 덧셈 자체는 안 넘쳐요. 그런데 MDN 오른쪽 시프트 문서대로 >> 는 피연산자를 32비트 정수로 바꿔서 계산해요. 알고리즘 문제 풀이에서 익힌 >> 1 습관이 서비스 코드에 들어가면 여기서 틀려요. >>> 1 도 2³² 를 넘으면 틀려서, lo=30억·hi=50억이면 >>> 1 은 1,852,516,352 를 냈어요. 큰 값에는 lo + Math.floor((hi - lo) / 2) 를 써요. 음수가 왜 나오는지는 2의 보수로 보면 바로 보여요(2진수·16진수 변환 원리 글, 진법 변환기에서 -397483648 을 32비트로 넣어 보세요).

파이썬은 정수 크기 제한이 없어 이 문제가 없고, Go sort.Search 는 uint 로 더해 피해요. C·C++ 의 부호 있는 정수 오버플로는 정의되지 않은 동작이라 lo + (hi - lo) / 2 로 써요.

운영에서 자주 나는 문제와 확인 순서, 체크리스트

이분 탐색 버그는 예외 없이 틀린 인덱스를 조용히 돌려주는 경우가 대부분이라, 증상보다 확인 순서를 정해 두는 편이 빨라요.

1. 정렬 기준과 비교 기준이 같은지. 가장 흔해요. DB 에서 대소문자 무시 정렬로 받아 온 목록을 대소문자 구분 비교로 찾거나, 숫자를 문자열로 정렬해 "10" < "9" 가 되는 경우예요. 로그 타임스탬프를 ISO 문자열로 찾을 때 +09:00 과 Z 표기가 섞이면 문자열 순서와 시간 순서가 어긋나요. 숫자 epoch 로 바꿔 찾되 초·밀리초를 섞지 않아요(초·밀리초 혼동 버그 글). 의심되는 값은 타임스탬프 변환기로 실제 시각을 확인해요.
2. 같은 값 중 무엇을 원했는지. 자바 binarySearch 결과로 "첫 위치"나 "개수"를 계산하고 있으면 고쳐요. 테스트 데이터에 중복이 없으면 통과하고 운영에서만 틀려요.
3. 끝 칸 처리. bisect_left 는 못 찾으면 len(a) 를 돌려줘요. a[i] 를 읽기 전에 i < len(a) 를 확인해요. 자바 음수 반환 r 은 -r - 1 이 삽입 위치예요.
4. 구간이 반복마다 줄어드는지. lo = mid 를 쓰면서 내림 mid 를 쓰면 원소 두 개 남았을 때 멈춰요. [1, 3] 에서 3 이하 마지막을 이렇게 찾는 코드는 2초 안에 끝나지 않았어요.
5. key 를 줄 때 x 도 key 값인지. 파이썬 bisect 문서는 3.10 에서 생긴 key 를 x 에는 적용하지 않는다고 적어요. bisect_left(rows, ts, key=lambda r: r.ts) 처럼 x 자리에 이미 뽑은 값을 넘겨요.

고친 뒤에는 작은 무작위 배열로 단순 반복문과 대조해요. 값 종류를 0~5 처럼 좁혀 중복과 빈 배열이 자주 나오게 하는 게 요령이에요.

import bisect, random

def last_le(a, x):                 # x 이하 마지막 인덱스, 없으면 -1
    return bisect.bisect_right(a, x) - 1

def oracle(a, x):
    idx = [i for i, v in enumerate(a) if v <= x]
    return idx[-1] if idx else -1

for _ in range(20_000):
    a = sorted(random.choices(range(6), k=random.randint(0, 6)))
    x = random.randint(-1, 6)
    assert last_le(a, x) == oracle(a, x), (a, x)

무한 루프가 걱정되면 반복 횟수 상한(64번 등)을 넘을 때 예외를 던지게 해 두면 테스트가 멈추지 않아요.

도입 전에 따질 것

직접 정렬 배열을 들고 이분 탐색을 하기 전에 아래를 확인해요.

• 수정 빈도: 위 계산대로 크기 × 1.3ns × 초당 수정 수가 CPU 몇 %인지 먼저 봐요. 1%를 넘으면 TreeMap 이나 일괄 재정렬로 가요.
• 질문 종류: 순서 질문이 없으면 해시가 빠르고 단순해요.
• 데이터 위치: 이미 DB 에 인덱스가 있으면 같은 일을 앱에 또 짤 이유가 거의 없어요. 앱 쪽 사본은 갱신 지연을 감수할 수 있는 읽기 전용일 때만이에요.
• 동시성: 정렬 리스트를 여러 스레드가 고치면 탐색과 삽입 사이에 위치가 바뀌어요. 통째로 새로 만들어 참조만 바꾸는(copy-on-write) 방식이 읽기 많은 경우에 단순해요.
• 기준 정렬 키: 문자열이면 어떤 비교(바이트, 로캘, 대소문자)로 정렬했는지 문서로 남겨요. 비교 기준이 바뀌면 데이터를 다시 정렬해야 해요.

자주 묻는 질문

값이 있는지만 확인하는데 이분 탐색을 써야 하나요?

순서 질문이 없으면 해시(set·HashSet)가 더 빨라요. 측정에서 100만 건 기준 파이썬 set 은 약 126ns, bisect 는 약 4,277ns 였어요. 다만 읽기만 하는 큰 데이터라 메모리가 빠듯하면 정렬 배열이 몇 배 적게 들어요.

bisect_left 와 bisect_right 는 언제 각각 쓰나요?

"x 이상 첫 위치"면 bisect_left, "x 초과 첫 위치"면 bisect_right 예요. x 의 개수는 둘의 차이, "x 이하 마지막"은 bisect_right - 1 이에요. 같은 값이 없는 데이터에서는 두 결과가 같아서 테스트에서 구분이 안 되니 중복 있는 입력으로 꼭 확인해요.

자바에는 lower_bound 가 없나요?

Arrays.binarySearch 는 같은 값 중 아무거나 돌려줘서 lower_bound 가 아니에요. 배열이면 반열린 구간 [lo, hi) 로 직접 짜고, 수정도 잦으면 TreeSet.ceiling·floor·subSet 을 써요. 직접 짠 코드는 무작위 대조 테스트로 확인해요.

파라메트릭 서치 범위는 어떻게 잡나요?

하한은 답이 될 수 없음을 증명할 수 있는 값, 상한은 답이 반드시 되는 값으로 잡아요. 넓게 잡아도 답은 같지만 판정 횟수가 늘어요. 예시 문제에서는 범위를 5억에서 1만으로 좁혀 판정이 29번에서 14번으로 줄었어요.

실수 이분 탐색은 몇 번 돌리면 되나요?

필요한 횟수는 ⌈log₂(범위/오차)⌉ 라서 0~10억을 10⁻⁶ 까지 줄여도 50번이에요. 100번 고정이면 대부분 넉넉해요. hi - lo > 1e-9 처럼 절대 오차로 멈추면 큰 값에서 무한 루프가 날 수 있어요.

정리

• 이분 탐색은 순서가 필요한 질문을, 거의 안 바뀌는 데이터에 쓸 때 가장 싸요. 있는지만 물으면 해시, 자주 바뀌면 TreeMap 이나 일괄 재정렬, 여러 서버가 보면 DB 인덱스예요.
• 같은 값 중 첫 위치가 필요하면 그걸 보장하는 함수(bisect_left, slices.BinarySearch, lower_bound)를 골라요.
• 파라메트릭 서치는 범위를 증명 가능한 값으로 좁히고, 실수는 반복 횟수로 멈추고, 값 범위가 크면 덧셈 오버플로를 확인해요.
• 고친 뒤에는 작은 무작위 배열 대조 테스트를 붙여요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 이분 탐색 lower_bound·upper_bound 경계 원리에서 도식과 코드로 단계별로 풀었어요.