퀴즈: 이분 탐색으로 범위 줄이기

후보가 4096개인 자료에서 범인 한 줄을 찾는다. 순차 탐색과 이분 탐색의 최악 횟수를 바르게 짝지은 것은?

• 순차 4096번, 이분 12번. 한 번 물을 때마다 후보가 절반이 되므로 올림한 log2(4096)이다
• 순차 4096번, 이분 64번. 이분 탐색의 횟수는 후보 수의 제곱근에 비례한다
• 순차 2048번, 이분 12번. 순차 탐색은 평균적으로 절반만 보면 되므로 후보의 절반이다
• 순차 4096번, 이분 2048번. 이분 탐색은 후보를 절반으로 한 번 줄이는 방법이다

빌드 이력을 이분하다가 가운데 판이 의존 모듈이 빠져 기동하지 않는다. 이 판을 '나쁨' 으로 세면 어떻게 되는가?

• 탐색이 그 자리에서 멈추고 아무 답도 나오지 않는다. 판정기는 세 갈래를 낼 수 없기 때문이다
• 경계가 앞쪽으로 밀려, 실제로는 멀쩡한 판이 처음 나빠진 판으로 지목될 수 있다
• 경계가 뒤쪽으로 밀리지만 전수 검증을 하지 않으면 드러나지 않아 결과는 안전하다
• 판정 결과와 무관하게 이분 탐색은 언제나 같은 판을 가리키므로 아무 영향이 없다

CSV 를 반씩 잘라 범인 행을 찾는데, 조각을 만들 때 머리글 줄을 빼먹었다. 무슨 일이 생기는가?

• 조각이 모두 통과해서 탐색이 범인을 찾지 못하고 마지막 행을 가리킨다
• 머리글이 없어도 파이썬 csv 모듈이 열 이름을 추론하므로 결과에는 영향이 없다
• 조각마다 첫 자료 행이 열 이름으로 읽혀 대부분의 조각이 실패하고, 탐색이 앞쪽 행을 범인으로 지목한다
• 조각의 행 수가 하나씩 어긋나므로 범인 행 번호가 정확히 1만큼 작게 나온다

이분 탐색으로 경계를 찾은 뒤 전수 검증을 해야 하는 이유로 가장 정확한 것은?

• 전수 검증을 해야 판정기가 실제로 실행됐다는 증거가 로그에 남기 때문이다
• 이분 탐색은 후보를 절반씩 버리므로 버린 쪽에 범인이 남아 있을 확률이 절반이기 때문이다
• 전수 검증의 비용이 이분 탐색보다 싸므로 애초에 이분 탐색을 할 이유가 없기 때문이다
• 경계 앞뒤가 갈린다는 전제가 깨진 이력에서는 이분 탐색이 조용히 틀린 답을 내놓기 때문이다

설정 항목 스무 개 중 어느 것이 문제인지 찾으려 한다. 이 후보들에는 시간 순서도 행 순서도 없다. 어떻게 접근하는 것이 맞는가?

• 후보에 순서가 없으므로 이분 탐색의 원리는 쓸 수 없고 하나씩 끄며 스무 번 확인해야 한다
• 항목을 절반씩 묶어 그 묶음을 통째로 꺼 보는 방식으로 같은 원리를 쓸 수 있다
• 항목 이름을 사전순으로 정렬하면 순서가 생기므로 그대로 이분 탐색을 적용하면 된다
• 설정은 서로 영향을 주므로 어떤 방식으로도 범위를 줄일 수 없고 전부 기본값으로 되돌려야 한다

두 행이 함께 들어 있을 때만 적재기가 죽는 자료가 있다. 여기에 행 단위 이분 탐색을 돌리면?

• 두 행 중 뒤쪽 행이 언제나 범인으로 지목되므로 답은 절반만 맞는다
• 조각을 나누는 순간 두 행이 갈라져 양쪽 다 통과하고, 탐색이 범인을 찾지 못하거나 엉뚱한 행을 가리킨다
• 이분 탐색은 조합을 모두 시험하므로 두 행을 함께 찾아내며 횟수만 두 배가 된다
• 적재기가 두 번 실패하므로 탐색이 두 개의 경계를 각각 정확히 보고한다