주문 내역 1만 건을 한 화면에 보여 줘야 한다. 행을 모두 DOM에 그리면 느려서, 화면에 보이는 행만 그리는 가상 리스트(virtual list)를 쓴다. 이때 스크롤할 때마다 묻는 질문이 있다. 지금 스크롤 위치(scrollTop, 아래 코드에서는 top)에서 화면 맨 위에 걸친 항목은 몇 번일까? 행 높이가 모두 같다면 나눗셈 한 번이면 된다. 그런데 펼쳐진 행, 사진이 있는 행처럼 높이가 제각각이면 앞에서부터 높이를 더해 가며 찾아야 할까? 스크롤 이벤트는 스크롤하는 동안 프레임마다 불릴 수 있는데(60fps면 초당 최대 60번), 불릴 때마다 1만 행을 훑는다면 아깝다.
이 장의 답은 이분 탐색(binary search)이다. 개념 정리는 이분 탐색, 가상 리스트 자체는 리스트 가상화 노트에 있다.
절반씩 버리기
항목마다 아래 끝 위치를 누적해 ends 배열을 한 번 만들어 둔다. 0번 항목 높이가 40px, 1번이 80px이면 ends는 [40, 120, …]이다. 높이는 음수가 아니니 ends는 정렬돼 있다. 정렬된 배열에서는 가운데 하나만 보면 절반을 버릴 수 있다. 가운데 항목의 아래 끝이 top보다 위(작거나 같음)라면 그 항목과 그 앞은 모두 이미 화면 위로 지나갔다. 아래(큼)라면 답은 그 항목이거나 그 앞이다.
한 번 비교할 때마다 후보가 절반이 된다. 1만 개는 14번, 100만 개는 20번이면 하나로 줄어든다( = 1,048,576). 이렇게 n을 절반으로 접어 1이 될 때까지의 횟수를 log₂ n이라 읽는다. 1만이면 1만 → 5천 → 2,500 → … → 1로 14번이다(2¹⁴ = 16,384가 1만을 넘는 첫 2의 거듭제곱. 『개발 수학』 Unit 2). 비교 횟수가 이라 O(log n)이다. 대신 조건이 하나 있다. 배열이 정렬돼 있어야 한다. 가운데 하나를 보고 한쪽을 통째로 버릴 수 있는 근거가 정렬이다.
경계 찾기: 조건이 처음 참이 되는 곳
이분 탐색을 "값 찾기"로 외우면 경계에서 틀리기 쉽다. 이 책은 하나의 모양으로 정리한다. 배열 위에 참·거짓 조건이 있고, 앞쪽은 모두 거짓, 뒤쪽은 모두 참일 때 처음 참이 되는 위치를 찾는다. 여기서 조건은 "ends[i] > top"(i번 항목의 아래 끝이 스크롤 위치 top보다 아래)이다.
- 답의 후보는
lo부터hi까지다. 처음엔lo = 0,hi = n(배열 길이)이다. 조건이 끝까지 거짓이면 답은 n, 곧 "보이는 항목 없음"이라서 n도 후보에 넣는다. mid에서 조건이 참이면 답은mid이하 →hi = mid.- 거짓이면 답은
mid + 1이상 →lo = mid + 1. lo === hi가 되면 멈춘다. 그 자리가 답이다.
항목별 아래 끝 위치 ends는 [40, 120, 160, 280, …]이다. 2번 항목은 120px에서 160px까지 차지한다. 스크롤 위치 top이 정확히 160일 때 화면 맨 위에 걸친 첫 항목은?
선택지와 해설 보기
실험 스크롤 위치에서 화면 맨 위 항목 찾기
ends[i]는 i번 항목의 아래 끝 위치(px)입니다. 맨 끝 칸 끝은 항목 수(10)를 뜻하는 자리로, 모든 항목이 화면 위로 지나갔을 때의 답입니다. 흐린 칸은 이미 버린 후보입니다.
const ends = [40, 120, 160, 280, 320, 380, 460, 500, 560, 640]const top = 170let lo = 0let hi = ends.lengthwhile (lo < hi) { const mid = Math.floor((lo + hi) / 2) if (ends[mid] > top) { hi = mid } else { lo = mid + 1 }}console.log(`첫 항목 ${lo}`)
아직 변수가 없습니다.
- 해볼 것
- top = 170 입력을 끝까지 실행해 비교 횟수를 세어 본다
- 경계값 top = 160 입력에서 2번 항목이 버려지는 이유를 본다
- 끝 너머 top = 700 입력에서 답이 10이 되는 것을 본다
top = 170과 top = 160은 둘 다 첫 항목 3을 찍는다. top = 700은 모든 ends보다 커서 lo가 끝까지 올라가 10이 된다.
top = 160에서 mid가 2를 가리킬 때 ends[2] > 160은 거짓이라 2번을 버리고, 답은 3번이 된다. 조건을 >=로 썼다면 2를 답으로 냈을 것이다. 경계값 하나 차이로 한 줄 위의 행이 그려지는 버그다. top이 모든 ends보다 크면 답은 n, 곧 "보이는 항목 없음"이다. 항목이 10개면 답 후보가 0~10의 11개라 비교는 많아야 네 번이다. 네 번 절반으로 줄이면 하나만 남는다(11 → 6 → 3 → 2 → 1, 네 번. = 16 ≥ 11).
mid는 Math.floor((lo + hi) / 2), Python은 (lo + hi) // 2로 구한다. lo < hi이면 mid는 언제나 lo 이상 hi 미만이라(lo = 3, hi = 4면 mid = 3), hi = mid든 lo = mid + 1이든 범위가 반드시 한 칸 이상 준다. 그래서 반복문이 끝난다.
표준 함수와 흔한 실수
Python에는 표준 라이브러리 bisect가 있다. bisect_right(a, x)는 앞쪽은 모두 x 이하, 뒤쪽은 모두 x보다 큰 경계, 곧 x보다 큰 첫 위치를 돌려준다. bisect_left(a, x)는 x 이상인 첫 위치다(Python 문서: bisect). 2절 반복문(조건 ends[i] > top)이 찾는 위치가 곧 bisect_right(ends, top)이고, 조건을 ends[i] >= top으로 쓰면 bisect_left(ends, top)의 답이 나온다. Python 3.10부터는 key 인자로 원소에서 비교할 값을 꺼낼 수 있다. JavaScript Array에는 이분 탐색 메서드가 없어 직접 짠다(MDN: Array).
// Array에 이분 탐색 메서드가 없어 직접 짠다function upperBound(xs: number[], x: number): number { let lo = 0, hi = xs.length while (lo < hi) { const mid = Math.floor((lo + hi) / 2) if (xs[mid] > x) hi = mid else lo = mid + 1 } return lo}upperBound(ends, 160) // 3
이분 탐색은 몇 줄 안 되지만 경계 하나만 어긋나도 틀린 답을 내거나 끝나지 않는다.
함정 찾기 AI가 짠 화면 맨 위 항목 찾기, 어디가 문제일까?
“항목 아래 끝 위치 배열
ends와 스크롤 위치 top을 받아, 화면 맨 위에 걸친 첫 항목 번호를 이분 탐색으로 찾는 함수를 짜 줘.”의심스러운 줄을 모두 눌러 표시한 뒤 “검토 끝”을 누르세요. 함정은 3개입니다.
정리하면 자주 틀리는 줄은 셋이다. hi = n - 1이면 "보이는 항목 없음"(n)을 못 내고, 조건이 >=면 이미 지나간 항목을 내며, lo = mid면 범위가 줄지 않아 끝나지 않는다.
정답을 이분 탐색하기
이분 탐색에 꼭 배열이 있어야 하는 것은 아니다. 필요한 것은 앞쪽은 모두 거짓, 뒤쪽은 모두 참인 조건 하나다. 이런 조건을 단조(monotonic) 조건이라고 한다.
git bisect가 좋은 예다. 커밋 이력은 정렬된 배열이 아니지만, "이 커밋에 버그가 있나"는 버그가 들어온 커밋부터 뒤로 모두 참이다. 그래서 버그가 없는 커밋(good)과 있는 커밋(bad)을 알려 주면 가운데 커밋을 하나씩 확인하며 처음 bad가 된 커밋을 찾는다(git-bisect 문서, git bisect 노트). 커밋 1,000개 사이라도 열 번 남짓 확인하면 된다.
"트럭 용량이 c면 기한 안에 다 보낼 수 있나"도 같다. 용량이 클수록 쉬워지므로 어떤 값부터 뒤로 모두 참이다. 답을 직접 계산하기 어려워도 "이 값이면 되나?"를 확인하기 쉬우면, 그 답을 이분 탐색할 수 있다. 이 방법을 매개 변수 탐색(parametric search)이라고 부른다. 보너스 문제가 이 모양이다.
확인 문제 장을 덮기 전에 떠올려 보기
1. 정렬된 원소 100만 개에서 이분 탐색으로 경계를 찾을 때 비교는 많아야 몇 번 정도일까?
2. while (lo < hi), 조건이 참이면 hi = mid인 이분 탐색에서 거짓일 때 lo = mid로 쓰면?
3. Python bisect_right(a, x)가 돌려주는 위치는? (a는 오름차순 정렬)
더 풀어 보기(선택) · 기한 안에 보내는 최소 트럭 용량
짐 무게 배열 weights를 순서를 바꾸지 않고 앞에서부터 하루에 한 트럭씩 보낸다. 하루에 실은 무게 합은 트럭 용량을 넘을 수 없고, 짐 하나를 쪼갤 수도 없다. days일 안에 모두 보낼 수 있는 가장 작은 트럭 용량을 구하자. 짐 n개, 무게 합 S일 때 O(n log S)로 풀어 보자(log S는 용량 후보 범위를 절반씩 줄이는 횟수).
weights = [3, 2, 2, 4, 1, 4], days = 3 → 6 (3 + 2 | 2 + 4 | 1 + 4)