---
title: "찾았는데 멈추면 안 되는 이유"
description: "정렬된 배열에 같은 값이 여러 개일 때 첫 자리를 찾는 문제입니다. 일반 이진 탐색이 왜 모자란지, 찾은 뒤 왼쪽으로 훑으면 왜 선형이 되는지, 그리고 한 줄만 바꾸면 그게 어떻게 사라지는지."
author: "유니얼"
pubDate: 2026-09-15
updatedDate: 2026-09-18
category: "programming/algorithm/search"
tags: ["탐색"]
canonical: https://blog.unialgames.com/posts/algo-lower-bound/
---
랭킹 보드에 점수가 정렬돼 있습니다. 같은 점수를 받은 사람이 여럿인데, 내 등수는 그중 **첫 번째 자리**여야 합니다.
레벨 10 이상인 유저가 몇 명인지 셀 때도 마찬가지입니다. 레벨 10이 몇 번째 자리에서 시작하는지를 알아야 합니다.

정렬된 배열이니 이진 탐색을 쓰면 될 것 같습니다. 그런데 이진 탐색을 그대로 쓰면 틀립니다.
값이 여러 개일 때 **그중 어느 것을 짚을지 정해져 있지 않기** 때문입니다.

## 찾으면 멈추는 탐색은 어느 것을 짚을지 모른다

```
인덱스   0  1  2  3  4  5
배열    [1, 3, 3, 3, 5, 7]     찾는 값 3
```

일반 이진 탐색을 돌려 보겠습니다.

<x-bisect>
<script type="application/json">
{
  "label": "찾으면 멈추는 방식",
  "array": [1, 3, 3, 3, 5, 7],
  "target": 3,
  "modes": ["plain"],
  "note": "칸 아래의 L 은 left, R 은 right, M 은 지금 보는 칸입니다"
}
</script>
</x-bisect>

가운데인 2번 칸이 마침 3이라 거기서 멈춥니다. 답으로 2를 내놓습니다.
**그런데 첫 번째 3은 1번 칸입니다.**

일반 이진 탐색이 답하는 것은 "있느냐 없느냐" 까지입니다.
중복이 있으면 어느 것을 짚을지는 배열 모양과 길이에 따라 달라집니다. 이 배열에서는 2였지만 다른 배열에서는 3일 수도 있습니다.

## 찾고 나서 왼쪽으로 훑으면

가장 먼저 떠오르는 수습책은 이것입니다. 찾은 자리에서 한 칸씩 왼쪽으로 가면서 값이 같은지 봅니다.

```
2번에서 찾음 → 1번도 3? 예, 계속 → 0번은 1? 다름, 멈춤 → 답 1
```

이 배열에서는 두 번만 훑으면 됩니다. 그래서 괜찮아 보입니다. 배열을 바꿔 보면 달라집니다.

```
배열 [3, 3, 3, ... , 3]     100만 칸이 전부 3
```

3을 찾아내는 것까지는 빠릅니다. 많아야 스무 번 비교면 됩니다.
그다음이 문제입니다. 찾은 자리에서 50만 번을 한 칸씩 왼쪽으로 훑습니다.
훑는 도중에도 값은 계속 3이라 멈출 이유가 없습니다.

| 항 | 뜻 | 100만 칸이 전부 같을 때 |
| --- | --- | --- |
| `log n` | 하나를 찾는 데 드는 비교 | 약 20 |
| `k` | 같은 값의 개수만큼 왼쪽으로 훑기 | 약 50만 |

그래서 이 방식의 비용은 `O(log n)` 이 아니라 **`O(log n + k)`** 입니다.
중복이 적으면 앞의 항이 커서 빨라 보이지만, `k` 가 커지면 뒤의 항이 전부를 먹습니다.
같은 값이 배열 전체에 깔리면 그냥 `O(n)` 입니다. 이진 탐색을 쓴 의미가 사라집니다.

**찾는 것은 여전히 빨랐습니다. 느려진 것은 훑는 부분입니다.**
그러니 고칠 곳도 찾는 쪽이 아니라 훑는 쪽입니다. 훑을 구간 자체가 안 생기게 만들면 됩니다.

## 같은 값을 만나도 멈추지 않는다

바꾸는 것은 한 줄입니다. **값을 찾아도 멈추지 않고, 오른쪽 경계를 그 자리로 당깁니다.**

같은 값이 깔린 구간도 이진 탐색의 대상이 됩니다. 매번 절반으로 줄어드니 훑을 일이 없습니다.

<x-bisect>
<script type="application/json">
{
  "label": "같은 값을 만나도 안 멈추는 방식",
  "array": [1, 3, 3, 3, 5, 7],
  "target": 3,
  "modes": ["lower"],
  "note": "오른쪽 끝의 점선 칸은 끝의 다음 자리입니다"
}
</script>
</x-bisect>

이 방식에 붙은 이름이 **lower_bound** 입니다. C++ 표준 라이브러리 함수 이름에서 왔고, 개념 자체는 언어와 무관합니다.
돌려주는 것은 "찾는 값 이상인 첫 자리" 입니다.

100만 칸이 전부 3인 배열에서도 스무 번쯤이면 끝납니다. 만날 때마다 오른쪽 경계가 절반으로 당겨지기 때문입니다.

## 훑지 않아도 첫 자리가 나오는 이유

여기서 걸리는 게 보통 둘입니다.

- 결국 같은 값이 깔린 구간을 다 보는 것 아닌가. 그러면 `O(log n + k)` 아닌가
- 값을 찾은 다음에 왼쪽으로 범위를 다시 잡아 훑는 것 아닌가

둘 다 아닙니다. **한 단계에 읽는 칸은 언제나 하나뿐**이고, 그 한 번으로 나머지 절반을 통째로 버립니다.
그리고 **구간은 줄어들기만 합니다.** 넓히는 일도, 찾은 뒤 다시 시작하는 일도 없습니다.
같은 값을 만나는 것은 특별한 사건이 아니라 여러 단계 중 하나일 뿐이고, 만날 때마다 그 자리에서 한쪽을 버리고 그대로 이어서 갑니다.

| | 실제로 읽는 칸 수 (100만 칸이 전부 3) |
| --- | --- |
| 찾고 왼쪽으로 훑기 | 20 + 50만 |
| 같은 값에서 안 멈추기 | 20 |

버리는 규칙은 두 줄입니다.

| `a[mid]` 가 | 버리는 것 | 왜 버려도 되나 |
| --- | --- | --- |
| target보다 작다 | mid와 그 왼쪽 전부 | 정렬돼 있으니 그 왼쪽은 전부 더 작습니다. target 이상인 자리가 있을 수 없습니다 |
| target 이상이다 | mid의 오른쪽 전부 | 거기에 같은 값이 더 있어도 mid보다 뒤입니다. **첫 자리가 될 수 없습니다** |

두 번째 줄이 "첫 번째" 를 만드는 규칙입니다. mid 자신은 아직 첫 자리일 수 있으니 남기고, 그 오른쪽만 버립니다.

같은 값을 여러 번 만나는 배열로 따라가 보겠습니다.

```
인덱스   0  1  2  3  4  5  6  7
배열    [1, 3, 3, 3, 3, 3, 5, 7]     찾는 값 3

left=0 right=8  mid=4  a=3   → right=4    5~7 버림, 4는 남김
left=0 right=4  mid=2  a=3   → right=2    3 버림, 2는 남김
left=0 right=2  mid=1  a=3   → right=1    2 버림, 1은 남김
left=0 right=1  mid=0  a=1   → left=1     0 버림
left=1 right=1  끝 → 답 1
```

3을 세 번 만났고 만날 때마다 오른쪽을 버렸습니다. 읽은 칸은 4번, 2번, 1번, 0번 **네 개뿐**입니다.
3이 다섯 개나 깔려 있는데 3번과 5번 칸은 손도 안 댔습니다.
5번이 3이라는 사실을 확인하지 않고 버렸지만 안전합니다. 4번보다 뒤라 첫 자리 후보에서 이미 탈락이기 때문입니다.

**답이 있을 수 없는 쪽만 버렸으니 답은 언제나 남은 구간 안에 있습니다.**
구간이 매번 절반이 되다가 폭이 0이 되면 갈 곳이 한 자리뿐이고, 그 자리가 답입니다.
그래서 마지막에 "이게 정말 첫 자리가 맞나" 를 확인하는 절차가 없습니다. 확인할 필요가 없습니다.

비교 횟수는 구간이 절반씩 줄어든 횟수, 즉 `log n` 입니다.
같은 값이 몇 개든 이 숫자는 안 변합니다. **`k` 가 식에 아예 안 들어옵니다.**

## 경계 두 개로 읽으면 전부 풀린다

코드는 이렇게 생겼습니다.

```csharp
int LowerBound(int[] a, int target) {
    int left = 0, right = a.Length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (a[mid] < target) left = mid + 1;
        else                 right = mid;
    }
    return left;
}
```

짧은데 헷갈립니다. `left` 와 `right` 를 **위치가 아니라 확정된 사실**로 읽으면 풀립니다.

| 변수 | 무엇이 확정됐다는 뜻인가 |
| --- | --- |
| `left` | 여기보다 왼쪽은 전부 찾는 값보다 작다 |
| `right` | 여기부터 오른쪽은 전부 찾는 값 이상이다 |

매 회 가운데 칸 하나를 보고 둘 중 하나를 확정합니다.

- `a[mid] < target` 이면 mid 도 작은 쪽이 확정입니다. **`left = mid + 1`**
- 아니면 mid 부터 오른쪽이 찾는 값 이상으로 확정입니다. **`right = mid`**

두 선이 만나면 그 지점이 "작은 것" 과 "이상인 것" 의 경계입니다. 그게 곧 첫 자리입니다.
손으로 따라가면 이렇습니다.

| 단계 | left | right | mid | a[mid] | 한 일 |
| --- | --- | --- | --- | --- | --- |
| 1 | 0 | 6 | 3 | 3 | 작지 않다. right 를 3으로 |
| 2 | 0 | 3 | 1 | 3 | 작지 않다. right 를 1로 |
| 3 | 0 | 1 | 0 | 1 | 작다. left 를 1로 |
| 4 | 1 | 1 | | | 둘이 만났다. 답은 1 |

2단계를 눈여겨볼 만합니다. mid 가 1이고 그 값이 3인데, 여기가 바로 정답 자리입니다.
**찾았다고 멈추지 않았기 때문에** 답이 확정된 채로 루프가 한 번 더 돕니다.

## 값이 없어도 실패하지 않는다

lower_bound 는 "못 찾았다" 를 돌려주지 않습니다. 언제나 **그 값이 들어가야 할 자리**를 돌려줍니다.

```
인덱스   0  1  2  3  4  5
배열    [1, 3, 3, 3, 5, 7]

lower_bound(3) → 1    3 이상인 첫 자리
lower_bound(4) → 4    4는 없지만 들어갈 자리
lower_bound(9) → 6    전부 작으니 끝의 다음
```

여기가 일반 이진 탐색과 가장 다른 점입니다. 있는지를 묻는 대신 **자리를 묻는 함수**입니다.
값이 실제로 있는지 알고 싶으면 돌려받은 자리를 한 번 더 확인하면 됩니다.

```csharp
int i = LowerBound(a, x);
bool found = i < a.Length && a[i] == x;
```

## 자주 틀리는 세 군데

같은 함수를 쓰면서 어긋나는 자리는 대체로 정해져 있습니다.

<x-compare>
<script type="application/json">
{
  "tabs": [
    {
      "label": "흔한 오답",
      "code": "int left = 0, right = a.Length - 1;\\nwhile (left <= right) {\\n    int mid = (left + right) / 2;\\n    if (a[mid] < target) left = mid + 1;\\n    else                 right = mid - 1;\\n}\\nreturn left;",
      "stats": [["[1,3,3,3,5,7] 에서 3", "운이 좋으면 맞음"], ["[1,3,5] 에서 9", "끝자리를 못 냄"], ["큰 배열", "오버플로 위험"]],
      "tone": "bad"
    },
    {
      "label": "제대로 된 판",
      "code": "int left = 0, right = a.Length;\\nwhile (left < right) {\\n    int mid = left + (right - left) / 2;\\n    if (a[mid] < target) left = mid + 1;\\n    else                 right = mid;\\n}\\nreturn left;",
      "stats": [["[1,3,3,3,5,7] 에서 3", "1"], ["[1,3,5] 에서 9", "3"], ["큰 배열", "안전"]],
      "tone": "good"
    }
  ]
}
</script>
</x-compare>

**`right = mid - 1` 로 쓰면 답을 건너뜁니다.** `a[mid]` 가 찾는 값 이상이면 mid 자신이 답일 수 있습니다.
left 와 right 를 따라간 표의 2단계가 그 경우입니다. 거기서 `right` 를 0으로 내렸다면 정답인 1번 칸이 구간 밖으로 밀려납니다.
`right` 는 버리는 선이 아니라 **지금까지 찾은 가장 왼쪽 후보**를 세워 두는 자리입니다.

**`right` 를 `a.Length - 1` 로 시작하면 끝자리를 못 냅니다.** 답이 배열 끝의 다음일 수 있기 때문입니다.

```
[1, 3, 5]   찾는 값 9   →  답은 3
```

9가 들어갈 자리는 3번, 즉 끝의 다음입니다. `right` 의 최댓값이 2면 이 답을 돌려줄 방법이 없습니다.
그래서 끝을 한 칸 열어 두고 `left < right` 로 돕니다.
애니메이션의 오른쪽 점선 칸이 그 자리입니다.

`mid` 를 `(left + right) / 2` 로 쓰는 것도 고쳐 둘 만합니다. 두 값이 큰 배열에서는 더하는 순간 넘칩니다.
`left + (right - left) / 2` 는 같은 값을 내면서 넘치지 않습니다.

## 조건 한 글자를 바꾸면 upper_bound

`a[mid] < target` 을 `a[mid] <= target` 으로 바꾸면 **찾는 값을 넘는 첫 자리**가 나옵니다.
이것이 upper_bound 입니다.

달라지는 것은 딱 하나, **같은 값을 만났을 때 어느 쪽을 버리느냐**입니다.

| `a[mid]` 가 | lower_bound | upper_bound |
| --- | --- | --- |
| target보다 작다 | 왼쪽을 버린다 | 왼쪽을 버린다 |
| **target과 같다** | **오른쪽을 버린다** | **왼쪽을 버린다** |
| target보다 크다 | 오른쪽을 버린다 | 오른쪽을 버린다 |

오른쪽을 버리면 계속 왼쪽으로 밀려가 첫 자리에 닿고, 왼쪽을 버리면 오른쪽으로 밀려가 마지막의 다음 자리에 닿습니다.
같은 배열에 upper_bound 를 돌리면 이렇게 갑니다.

```
[1, 3, 3, 3, 5, 7]   찾는 값 3

left=0 right=6  mid=3  a=3 같다  → left=4    0~3 버림
left=4 right=6  mid=5  a=7 크다  → right=5   5~6 버림
left=4 right=5  mid=4  a=5 크다  → right=4
left=4 right=4  끝 → 답 4
```

| | 돌려주는 것 | 위 배열에서 3을 넣으면 |
| --- | --- | --- |
| `lower_bound(x)` | x 이상인 첫 자리 | 1 |
| `upper_bound(x)` | x 를 넘는 첫 자리 | 4 |

두 값을 빼면 **그 값의 개수**가 됩니다. `4 - 1 = 3` 이고, 실제로 3이 세 개입니다.
"레벨 10 이상 20 미만인 유저 수" 도 같은 방식으로 `lower_bound(20) - lower_bound(10)` 입니다.
세지 않고 빼기 한 번으로 나옵니다.

## C# 에는 lower_bound 가 없다

표준 함수가 없어서 `Array.BinarySearch` 를 대신 쓰게 되는데, 동작이 다릅니다.

```csharp
int idx = Array.BinarySearch(arr, x);
if (idx < 0) idx = ~idx;   // 못 찾으면 들어갈 자리의 보수를 돌려준다
```

값이 없을 때는 이걸로 충분합니다. `~idx` 가 곧 삽입 위치이고 lower_bound 와 같은 값입니다.
문제는 값이 있을 때입니다. **중복이 있으면 그중 어느 것을 돌려줄지 보장하지 않습니다.**
첫 자리라는 보장이 없으니, 앞의 문제를 그대로 다시 만나게 됩니다.

`List<T>.BinarySearch` 도 같습니다. 중복이 있을 수 있는 데이터에서 첫 자리가 필요하면 위의 짧은 함수를 직접 두는 편이 안전합니다.

## 어디에 쓰나

- **정렬을 유지하며 넣을 자리 찾기.** 쿨타임이 끝나는 순서로 스킬을 꽂아 두는 큐, 점수순 랭킹 보드가 그렇습니다
- **범위 세기.** 두 경계를 빼면 그 구간의 개수가 나옵니다. 순회가 필요 없습니다
- **좌표 압축.** 값이 띄엄띄엄한 좌표들을 정렬해 두고 "이 값이 몇 번째" 로 바꿔 배열 인덱스로 쓸 때
- **가장 긴 증가 부분 수열.** 이 문제를 `O(n log n)` 으로 푸는 풀이의 안쪽이 lower_bound 입니다

전제는 하나뿐입니다. **범위가 정렬돼 있어야 합니다.** 정렬 안 된 배열에 돌리면 결과에 아무 의미가 없고, 에러도 안 납니다.

## 정리

중복이 있는 정렬 배열에서 첫 자리를 찾는 문제는 이진 탐색을 한 줄 고쳐서 풉니다.

```
찾으면 멈춘다   →   같아도 안 멈추고 right = mid 로 당긴다
```

이 한 줄이 `O(log n + k)` 를 `O(log n)` 으로 바꿉니다. 훑을 구간이 아예 안 생기기 때문입니다.

읽을 때 챙길 것은 넷입니다.

- **`left` 와 `right` 는 위치가 아니라 확정된 사실입니다.** 왼쪽은 전부 작고, 오른쪽은 전부 이상입니다. 둘이 만나는 자리가 답입니다
- **구간은 줄어들기만 합니다.** 답이 있을 수 없는 쪽만 버리므로, 마지막에 남은 자리가 답인지 따로 확인할 필요가 없습니다
- **`right = mid` 이고 `right` 의 시작은 `a.Length` 입니다.** mid 자신이 답일 수 있고, 답이 배열 끝의 다음일 수도 있습니다
- **조건 한 글자를 바꾸면 upper_bound 가 되고, 둘을 빼면 개수가 나옵니다**