---
title: "반으로 자르면 백만 칸이 스무 번에 끝난다"
description: "이진 탐색의 기본형입니다. 구간을 닫힌 것으로 잡을지 열린 것으로 잡을지, 언제 멈출지, 그리고 무한 루프와 오버플로가 나는 자리를 봅니다."
author: "유니얼"
pubDate: 2026-09-16
updatedDate: 2026-09-18
category: "programming/algorithm/search"
tags: ["탐색"]
canonical: https://blog.unialgames.com/posts/algo-binary-search/
---
정렬된 배열에서 값 하나를 찾습니다. 앞에서부터 훑으면 100만 칸짜리 배열에서 최악에 100만 번 비교합니다.
가운데를 한 번 보고 절반을 버리면 스무 번입니다.

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

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

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

<x-bisect>
<script type="application/json">
{
  "label": "직접 굴려보기",
  "array": [2, 5, 8, 12, 16, 23, 38, 56, 72, 91],
  "target": 23,
  "modes": ["plain"],
  "note": "칸 아래의 L 은 left, R 은 right, M 은 지금 보는 칸입니다"
}
</script>
</x-bisect>

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

| 칸 수 | 앞에서부터 훑기 (최악) | 반으로 자르기 |
| --- | --- | --- |
| 1,000 | 1,000 | 10 |
| 100만 | 100만 | 20 |
| 10억 | 10억 | 30 |

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

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

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

<x-compare>
<script type="application/json">
{
  "tabs": [
    {
      "label": "닫힌 구간 [left, right]",
      "code": "int left = 0, right = a.Length - 1;\\n\\nwhile (left <= right) {\\n    int mid = left + (right - left) / 2;\\n\\n    if (a[mid] == target) return mid;\\n    if (a[mid] < target) left = mid + 1;\\n    else                 right = mid - 1;\\n}\\n\\nreturn -1;",
      "stats": [["right 의 시작", "Length - 1"], ["루프 조건", "left <= right"], ["갱신", "mid + 1 / mid - 1"]]
    },
    {
      "label": "열린 구간 [left, right)",
      "code": "int left = 0, right = a.Length;\\n\\nwhile (left < right) {\\n    int mid = left + (right - left) / 2;\\n\\n    if (a[mid] == target) return mid;\\n    if (a[mid] < target) left = mid + 1;\\n    else                 right = mid;\\n}\\n\\nreturn -1;",
      "stats": [["right 의 시작", "Length"], ["루프 조건", "left < right"], ["갱신", "mid + 1 / mid"]]
    }
  ]
}
</script>
</x-compare>

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

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

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

## 무한 루프가 나는 자리

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

```csharp
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` 로 쓰면 답이 될 수 있는 칸을 버립니다.

| 구간 | 작을 때 | 클 때 | 루프 조건 |
| --- | --- | --- | --- |
| 닫힌 `[left, right]` | `left = mid + 1` | `right = mid - 1` | `left <= right` |
| 열린 `[left, right)` | `left = mid + 1` | `right = mid` | `left < right` |

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

## mid 를 계산하는 법

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

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

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

## 전제와 비용

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

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

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

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

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

## 정리

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

쓸 때 정할 것은 셋입니다.

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