---
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-on-answer/
---
씬을 로딩할 때 에셋을 몇 개씩 묶어서 올릴지 정해야 합니다. 한 번에 많이 올리면 빨리 끝나지만 프레임이 튑니다.
적게 올리면 부드러운 대신 로딩이 깁니다. **프레임을 16ms 아래로 유지하면서 가장 크게 잡을 수 있는 묶음 크기**를 찾고 싶습니다.

이건 배열에서 값을 찾는 문제가 아닙니다. 그런데도 이분 탐색이 그대로 먹힙니다.
성질 하나만 있으면 됩니다. **한 번 안 되기 시작하면 그 뒤로는 계속 안 된다는 것**입니다.

## 되고 안 되고를 늘어놓으면 배열이 된다

묶음 크기를 1부터 올려 가며 되는지 표시하면 이렇게 생겼습니다.

```
묶음 크기   1  2  3  4  5  6  7  8
16ms 이하   O  O  O  O  X  X  X  X
```

크기를 키울수록 무거워지니 **O 다음에 X 가 나오면 다시 O 로 돌아오지 않습니다.**
이렇게 한 방향으로만 바뀌는 성질을 단조롭다고 합니다.

O 와 X 가 갈리는 경계를 찾는 일은, 0과 1이 늘어선 배열에서 1이 처음 나오는 자리를 찾는 것과 똑같습니다.

<x-bisect>
<script type="application/json">
{
  "label": "판정을 늘어놓고 경계 찾기",
  "array": [0, 0, 0, 0, 1, 1, 1, 1],
  "target": 1,
  "modes": ["lower"],
  "note": "0 이 16ms 이하, 1 이 초과입니다. 이 배열은 실제로 만들지 않고 물어볼 때마다 판정합니다"
}
</script>
</x-bisect>

다른 점이 하나 있습니다. **이 배열은 메모리에 없습니다.**
`a[mid]` 를 읽는 대신 그 크기로 실제로 돌려 보고 되는지 묻습니다. 나머지 절차는 같습니다.

## 코드는 판정 함수 하나만 갈아 끼운다

```csharp
int MinFeasible(int lo, int hi, Func<int, bool> ok) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (ok(mid)) hi = mid;      // 되는 값이니 답 후보로 남긴다
        else         lo = mid + 1;  // 안 되면 이 값 이하는 전부 탈락
    }
    return lo;
}
```

`ok` 가 배열 접근 자리를 대신합니다. 여기서는 "이 묶음 크기로 올렸을 때 프레임이 16ms 이하인가" 입니다.
이렇게 답의 범위를 이분 탐색하는 것에 붙은 이름이 **파라메트릭 서치(parametric search)** 입니다.

**찾는 것이 최댓값이면 판정을 뒤집습니다.** 위 예는 "무거워지는 쪽" 이라 O 가 앞에 오니,
"O 인 것 중 가장 큰 값" 은 `MinFeasible` 이 돌려준 첫 X 자리에서 하나 뺀 값입니다.
헷갈리면 조건을 반대로 세우는 대신 **찾은 경계에서 한 칸 물러나는 쪽**이 실수가 적습니다.

## 어디에 쓰나

경계가 궁금한 설정값은 대체로 이 모양입니다.

| 찾는 것 | 판정 |
| --- | --- |
| 로딩 청크 크기 | 이 크기로 올리면 프레임이 예산 안에 드는가 |
| 동시 스폰 한도 | 이만큼 띄워도 목표 프레임이 유지되는가 |
| 텍스처 해상도 | 이 해상도로 메모리 한도 안에 들어가는가 |
| 스킬 사거리 | 이 사거리면 적이 반격 전에 닿는가 |

**판정 한 번이 비싸다는 것이 이 방식의 특징입니다.** 배열 접근은 나노초지만 여기서는 실제로 돌려 봐야 합니다.
그래서 비교 횟수를 줄이는 것이 그대로 시간이 됩니다. 후보가 1,000가지여도 열 번만 재면 됩니다.

## 실수 범위는 반복 횟수로 끊는다

묶음 크기는 정수지만 사거리나 각도는 실수입니다. 실수에는 "다음 값" 이 없어서 `lo < hi` 로는 안 끝납니다.

```csharp
float lo = 0f, hi = 100f;

for (int i = 0; i < 60; i++) {      // 횟수를 고정한다
    float mid = (lo + hi) / 2f;
    if (ok(mid)) hi = mid;
    else         lo = mid;
}

return hi;
```

`hi - lo < 0.001f` 같은 조건도 되지만 **반복 횟수를 고정하는 쪽이 안전합니다.**
부동소수 오차 때문에 조건이 영영 안 만족되는 경우가 생기기 때문입니다.
한 번에 절반이니 예순 번이면 어떤 범위든 충분히 좁혀집니다.

## 단조롭지 않으면 못 쓴다

이 방식이 성립하는 이유는 **한 번 X 가 나오면 그 뒤로 전부 X 라는 보장** 하나뿐입니다. 그 보장이 없으면 답이 엉뚱하게 나옵니다.

게임에서 이 전제가 깨지는 자리가 실제로 있습니다.

- **측정값으로 판정할 때.** 프레임 시간은 잴 때마다 흔들립니다. 경계 근처에서 한 번 운 좋게 통과하면 그 위쪽을 통째로 버립니다
- **효과가 계단식일 때.** 텍스처 크기는 2의 제곱에서 메모리가 꺾입니다. 중간값은 의미가 없습니다
- **두 자원이 반대로 움직일 때.** 크게 잡으면 CPU 가 편해지고 GPU 가 힘들어지는 식이면 하나의 판정으로 안 됩니다

측정으로 판정할 때는 **한 번 재고 넘어가지 말고 여러 번 재서 중앙값을 쓰거나, 경계에 여유를 두는 편**이 낫습니다.
16ms 를 기준으로 하면서 실제로는 14ms 로 잡는 식입니다. 노이즈가 신호보다 크면 이분 탐색이 아니라 측정을 먼저 고쳐야 합니다.

## 정리

찾는 대상이 배열 안에 없어도 이분 탐색을 쓸 수 있습니다. 필요한 것은 **판정이 한 방향으로만 바뀐다는 성질**입니다.

- 되는 값과 안 되는 값을 늘어놓으면 0과 1이 늘어선 배열이 되고, 경계를 찾는 일은 첫 1을 찾는 일과 같습니다
- 배열 접근 자리에 판정 함수를 넣습니다. 판정이 비쌀수록 이 방식이 이득입니다
- 실수 범위에서는 조건 대신 반복 횟수를 고정합니다
- **판정이 흔들리면 쓰면 안 됩니다.** 측정으로 판정할 때는 노이즈부터 줄이고 시작합니다