탐색
6편
꼭짓점은 양 끝이 아니라 두 점을 비교해서 찾는다
올라갔다 내려오는 곡선의 최고점을 찾는 문제입니다. 크다 작다로는 방향을 알 수 없어서, 가운데 두 점을 견줘 삼분의 일씩 버립니다. 그 전제가 깨지는 자리까지.
한 바퀴 돌아간 배열에서도 반쪽은 정렬돼 있다
링 버퍼처럼 어느 지점에서 끊긴 정렬 배열에서 값을 찾습니다. 가운데를 보면 두 반쪽 중 하나는 반드시 정렬돼 있고, 그 사실 하나로 절반을 버릴 수 있습니다.
배열이 아니라 답을 이분 탐색한다
찾는 대상이 배열의 값이 아니라 설정값일 때도 반으로 자를 수 있습니다. 판정이 단조롭기만 하면 됩니다. 그 전제가 깨지는 자리와 실수 범위를 다루는 법까지.
끝이 어딘지 모르는 배열에서 찾기
길이를 알려주지 않는 정렬된 데이터에서 값을 찾는 지수 탐색(exponential search)입니다. 경계를 두 배씩 넓혀 구간부터 만든 다음 이진 탐색으로 넘기는 방법과, 그 비용이 왜 전체 크기와 무관한지.
찾았는데 멈추면 안 되는 이유
정렬된 배열에 같은 값이 여러 개일 때 첫 자리를 찾는 문제입니다. 일반 이진 탐색이 왜 모자란지, 찾은 뒤 왼쪽으로 훑으면 왜 선형이 되는지, 그리고 한 줄만 바꾸면 그게 어떻게 사라지는지.
반으로 자르면 백만 칸이 스무 번에 끝난다
이진 탐색의 기본형입니다. 구간을 닫힌 것으로 잡을지 열린 것으로 잡을지, 언제 멈출지, 그리고 무한 루프와 오버플로가 나는 자리를 봅니다.