반으로 자르면 백만 칸이 스무 번에 끝난다

정렬된 배열에서 값 하나를 찾습니다. 앞에서부터 훑으면 100만 칸짜리 배열에서 최악에 100만 번 비교합니다. 가운데를 한 번 보고 절반을 버리면 스무 번입니다.

2의 20제곱이 약 100만입니다. 반으로 자르는 횟수가 곧 비교 횟수라서, 배열이 열 배가 되어도 비교는 서너 번만 늘어납니다. 이게 이진 탐색(binary search) 이고, 성립하려면 조건이 하나 있습니다. 배열이 정렬돼 있어야 합니다.

한 번 비교에 절반이 사라진다

절차는 셋입니다. 가운데 칸을 본다, 찾는 값과 비교한다, 답이 있을 수 없는 절반을 버린다.

열 칸짜리 배열에서 비교 세 번이면 끝납니다. 앞에서부터 훑었다면 여섯 번 봐야 했습니다. 칸이 늘어날수록 이 차이가 벌어집니다.

10억 칸에서 서른 번입니다. 칸이 천 배가 되어도 비교는 열 번 늘어납니다.

구간을 어떻게 잡느냐가 나머지를 정한다

코드가 헷갈리는 이유는 구간을 잡는 방식이 둘이기 때문입니다. 둘은 짝이 맞아야 합니다. 조건, 갱신, 종료가 한 세트라 하나만 섞어도 어긋납니다.

닫힌 구간은 right 가 후보를 가리킵니다. 그 칸도 아직 볼 자리라 right - 1 로 내려야 하고, 칸이 하나 남은 left == right 도 검사해야 하니 조건이 <= 입니다.

열린 구간은 right 가 후보의 바로 다음을 가리킵니다. 그래서 right = mid 로 당기고, left == right 면 남은 칸이 없다는 뜻이라 조건이 < 입니다.

값이 있는지만 볼 때는 어느 쪽이든 됩니다. 다만 “없으면 들어갈 자리” 가 필요해지는 순간 열린 구간이 편합니다. 답이 배열 끝의 다음일 수 있는데, right 의 최댓값이 Length - 1 이면 그 자리를 가리킬 수가 없습니다.

무한 루프가 나는 자리

이진 탐색에서 가장 흔한 사고입니다. 구간이 줄어들지 않는 갱신을 쓰면 루프가 안 끝납니다.

if (a[mid] < target) left = mid;    // 여기가 문제
else                 right = mid;

칸이 둘 남았을 때를 따라가면 보입니다. left = 3, right = 4 면 mid = 3 + (4 - 3) / 2 = 3 입니다. a[3] 이 작아서 left = mid 로 두면 left 는 그대로 3이고, 다음 회차의 mid 도 다시 3입니다. 영원히 같은 칸을 봅니다.

버릴 때는 방금 본 칸을 반드시 구간에서 빼야 합니다. a[mid] 가 찾는 값보다 작다면 mid 자신도 답이 아니니 mid + 1 로 넘깁니다.

반대쪽도 짝이 맞아야 합니다. 닫힌 구간에서 right = mid 로 쓰면 같은 이유로 안 끝나고, 열린 구간에서 right = mid - 1 로 쓰면 답이 될 수 있는 칸을 버립니다.

이 표의 한 줄을 통째로 쓰세요. 두 줄에서 하나씩 가져오면 어긋납니다.

mid 를 계산하는 법

(left + right) / 2 는 값이 클 때 더하는 순간 넘칩니다. int 는 약 21억까지인데 두 인덱스가 각각 15억이면 합이 30억이라 음수가 되고, 음수 인덱스로 접근하면서 터집니다.

int mid = left + (right - left) / 2;

빼서 절반을 구한 뒤 더하면 넘칠 일이 없습니다. 결과는 같습니다. 배열 인덱스로 쓰는 동안은 21억 칸짜리 배열을 만들 일이 없어서 드물지만, 답 자체를 이분 탐색할 때는 큰 수를 다루게 되므로 습관으로 두는 편이 낫습니다.

전제와 비용

성립 조건은 하나입니다. 정렬돼 있어야 합니다. 정렬 안 된 배열에 돌리면 엉뚱한 답을 내면서 에러도 안 납니다.

그래서 판단할 것이 하나 더 생깁니다. 정렬 비용을 누가 내느냐입니다.

• 한 번 정렬해 두고 여러 번 찾는다면 이득입니다. 정렬 O(n log n) 을 한 번 내고 조회마다 O(log n)
• 매번 정렬해서 한 번 찾는다면 손해입니다. 그냥 훑는 것이 빠릅니다
• 데이터가 자주 바뀐다면 정렬을 유지하는 비용을 봐야 합니다. 배열 가운데에 넣는 것은 O(n) 입니다

그리고 작은 배열에서는 그냥 훑는 쪽이 빠릅니다. 열 칸짜리면 이진 탐색의 분기와 인덱스 계산이 단순 비교 열 번보다 무겁고, 배열은 메모리가 붙어 있어서 앞에서부터 읽는 것이 캐시에 유리합니다. 경계가 어디인지는 기기와 자료형에 따라 다르니 재 봐야 나옵니다.

값을 키로 자주 찾는데 순서는 필요 없다면 Dictionary 가 낫습니다. 평균 조회가 O(1) 입니다. 이진 탐색이 값을 하는 자리는 순서가 필요할 때입니다. 범위로 자르거나, 가장 가까운 값을 찾거나, 들어갈 자리를 물을 때입니다.

정리

이진 탐색은 한 번 비교로 절반을 버리는 방식입니다. 비교 횟수가 log n 이라 100만 칸이 스무 번, 10억 칸이 서른 번입니다.

쓸 때 정할 것은 셋입니다.

• 구간을 닫힌 것으로 잡을지 열린 것으로 잡을지. 조건과 갱신과 종료가 한 세트라 섞으면 어긋납니다
• 방금 본 칸을 구간에서 빼는지. 안 빼면 같은 칸을 영원히 봅니다
• 정렬 비용을 누가 내는지. 한 번 정렬하고 여러 번 찾을 때만 이득입니다