반씩 자르면 64판이 여섯 번이다

한 줄 요약

이분 탐색은 도구가 아니라 절차다. 좋다와 나쁘다를 기계가 가를 수 있게 만드는 순간, 64판의 이력도 4096행의 자료도 여섯 번과 열두 번으로 줄어든다.

왜 이게 필요했나

현장에서 가장 자주 듣는 두 문장이 있다. "지난주까지는 됐는데요" 와 "어제 들어온 파일에서만 죽어요" 다. 둘은 전혀 다른 말처럼 들리지만 구조가 같다. 어딘가에 경계가 하나 있고, 그 앞은 괜찮고 뒤는 괜찮지 않다. 우리가 찾는 것은 그 경계다.

경계를 찾는 가장 자연스러운 방법은 앞에서부터 하나씩 보는 것이다. 빌드 64판을 하나씩 돌리면 최악의 경우 64번이고, 한 번에 30초가 걸린다면 32분이다. 자료 4096행을 한 줄씩 넣어 보면 4096번이다. 여기에 고객사 담당자가 옆에서 기다리고 있다.

반씩 자르면 숫자가 달라진다. 후보가 63개면 여섯 번, 4096개면 열두 번, 100만 개라도 스무 번이다. 후보가 두 배가 될 때마다 늘어나는 횟수는 하나다. 이 성질이 현장에서 하는 일의 성격을 바꾼다 — 자료가 커질수록 순차 탐색과의 차이는 벌어지기만 한다.

어떻게 동작하나

이분 탐색이 성립하려면 세 가지가 있어야 한다.

첫째, 기계가 판정할 수 있어야 한다. "좀 이상해 보인다" 는 판정이 아니다. 판정기는 입력을 받아 좋다·나쁘다 중 하나를 내놓는 프로그램이어야 하고, 사람이 화면을 보고 고개를 갸웃하는 절차가 섞이면 스무 번을 반복할 수 없다. [git bisect](https://git-scm.com/docs/git-bisect) 가 git bisect run <스크립트> 라는 형태를 가진 이유가 여기 있다. 그 규약에서 종료 코드 0 은 좋음, 1에서 124 사이는 나쁨, 125 는 판정 불가(건너뛰기) 다. 우리 실습도 같은 약속을 쓴다.

둘째, 성질이 단조여야 한다. 경계 앞은 전부 좋고 뒤는 전부 나빠야 한다. 중간에 고쳤다가 다시 깨진 이력이라면 이분 탐색은 "처음 나빠진 판" 이 아니라 "어떤 나쁜 판" 을 준다. 자료 쪽도 마찬가지다. 한 행이 혼자 죽이는 경우는 단조지만, 두 행이 함께 있을 때만 죽는 경우는 단조가 아니라 조각을 나누는 순간 둘이 갈라져 양쪽 다 통과한다.

셋째, 후보에 순서가 있어야 한다. 빌드는 시간 순서가 있고, 파일은 행 순서가 있다. 순서가 없는 후보(설정 항목 스무 개)는 이분이 아니라 묶어서 절반씩 끄는 방식으로 같은 원리를 쓴다.

파이썬 표준 라이브러리의 [bisect 모듈](https://docs.python.org/3/library/bisect.html)은 정렬된 배열에서 값의 자리를 찾는 함수를 준다. 우리가 하는 일은 배열 대신 판정기를 부르는 탐색이고, 뼈대는 같다. 알려진 좋은 자리를 lo, 알려진 나쁜 자리를 hi 로 두고, 사이가 한 칸이 될 때까지 가운데를 물어 한쪽을 당긴다. 후보가 n 개일 때 필요한 물음의 수는 올림한 log2(n) 이다 — 한 번 물을 때마다 후보가 절반이 되므로, n 을 1로 만들려면 2를 몇 번 곱해 n 이 되는지를 세면 된다.

후보 63개   →  6번      후보 4096개 →  12번후보 100만개 → 20번      후보 10억개  →  30번

판정 불가는 특별한 값이다. 기동하지 않는 빌드, 의존 모듈이 빠진 판, 그날만 네트워크가 죽어 있던 판이 여기 속한다. 이것을 "나쁨" 으로 셈하면 경계가 앞으로 밀려 엉뚱한 판을 범인으로 지목한다. 그래서 세 번째 값을 두고, 만나면 이웃으로 한 칸 비켜 다시 묻는다. 구간이 통째로 판정 불가면 한 판을 지목하지 않고 남은 구간을 그대로 보고한다. 범위를 좁힌 것도 성과다.

현장에서 만나는 모습

첫째, 판정기를 만들기 전에 탐색부터 시작한다. 가운데 판을 돌려 보고 "음, 느린 것 같기도 하고" 하면서 눈으로 판정하면, 열 번쯤 지났을 때 자기가 어느 쪽을 좋다고 했는지 기억나지 않는다. 판정기를 먼저 만들면 탐색은 반복문일 뿐이다.

둘째, 경계를 찾고 검증하지 않는다. 탐색은 로그지만 검증은 선형이다. 경계 뒤의 판을 전수로 돌려 전부 나쁜지 확인하는 데 드는 비용은 처음부터 순차 탐색을 한 것과 같다. 그래도 한 번은 해야 한다 — 단조가 아닌 이력에서 이분 탐색은 조용히 틀린 답을 주기 때문이다. 시간이 없으면 최소한 경계 판이 나쁜지와 그 앞 판이 좋은지 두 번은 확인한다.

셋째, 자료 쪽 이분에서 머리글을 잃어버린다. CSV 를 반으로 자르면서 머리글을 떼면 뒤쪽 조각은 첫 행을 열 이름으로 읽어 엉뚱하게 실패한다. 그러면 모든 조각이 나쁨이 되어 탐색이 1행을 가리킨다. 조각을 만들 때는 머리글을 항상 붙인다.

넷째, 횟수를 세지 않는다. 보고서에 "이분 탐색으로 찾았습니다" 라고만 적으면 고객은 그 절차의 값어치를 모른다. "후보 4096개를 12번 만에 좁혔습니다" 라고 적으면 다음에도 같은 절차를 쓰자는 말이 나온다. 숫자가 방법을 판다.

실무에서 진짜 중요한 것

• 판정기가 먼저다. 좋다와 나쁘다를 기계가 가르지 못하면 탐색은 시작할 수 없다.
• 판정 불가를 나쁨으로 접지 않는다. 세 번째 값을 두고 이웃으로 비켜 간다.
• 단조를 의심한다. 경계를 찾은 뒤 최소 두 번, 가능하면 전수로 확인한다.
• 횟수를 기록한다. 순차라면 몇 번이었는지를 함께 적어야 절차가 팔린다.

다음 실습에서 할 것

고객사 빌드 64판과 새 입력 4096행을 손에 쥐고, 좋다·나쁘다·판정 불가를 가르는 판정기를 먼저 만든다. 그 판정기로 이력을 반씩 잘라 처음 나빠진 판을 찾고, 기동하지 않는 판을 만났을 때 비켜 가는 길을 붙인다. 같은 원리를 자료에 적용해 적재기를 죽이는 행을 열두 번 만에 찾고, 경계가 정말 경계인지 전수로 검증한 뒤, 순차라면 몇 번이었을지를 함께 적어 한 장으로 보고한다.