---
title: "한 바퀴 돌아간 배열에서도 반쪽은 정렬돼 있다"
description: "링 버퍼처럼 어느 지점에서 끊긴 정렬 배열에서 값을 찾습니다. 가운데를 보면 두 반쪽 중 하나는 반드시 정렬돼 있고, 그 사실 하나로 절반을 버릴 수 있습니다."
author: "유니얼"
pubDate: 2026-09-16
updatedDate: 2026-09-18
category: "programming/algorithm/search"
tags: ["탐색"]
canonical: https://blog.unialgames.com/posts/algo-search-rotated/
---
최근 로그 1,000줄을 링 버퍼에 담아 둡니다. 꽉 차면 가장 오래된 줄부터 덮어쓰니, 배열 어딘가에서 시간이 한 번 끊깁니다.

```
인덱스   0   1   2   3   4   5   6   7
시각    [50, 60, 70, 80, 10, 20, 30, 40]
                        ↑ 여기서 끊긴다
```

전체로 보면 정렬이 아닙니다. 그래도 **원래 정렬된 배열을 어느 지점에서 잘라 앞뒤를 바꾼 모양**이라는 성질이 남아 있습니다.
이런 배열을 **회전된 정렬 배열(rotated sorted array)** 이라고 부릅니다.
그 성질만으로 이분 탐색이 그대로 됩니다.

## 가운데를 보면 한쪽은 반드시 정렬돼 있다

끊긴 자리는 하나뿐입니다. 그러니 가운데에서 배열을 둘로 나누면 **끊긴 자리는 둘 중 한쪽에만 들어갑니다.**
남은 한쪽은 통째로 정렬돼 있습니다.

정렬된 쪽인지는 양 끝을 비교하면 알 수 있습니다.

| 조건 | 뜻 |
| --- | --- |
| `a[lo] <= a[mid]` | 왼쪽 반쪽이 정렬돼 있다 |
| 아니면 | 오른쪽 반쪽이 정렬돼 있다 |

정렬된 쪽은 **첫 값과 끝 값만 보면 찾는 값이 그 안에 있는지 알 수 있습니다.**
있으면 그쪽으로 좁히고, 없으면 반대쪽으로 갑니다. 반대쪽은 끊긴 자리를 품고 있지만 상관없습니다.
다음 회차에서 다시 반으로 나누면 또 한쪽은 정렬돼 있습니다.

```csharp
int Search(int[] a, int target) {
    int lo = 0, hi = a.Length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;

        if (a[lo] <= a[mid]) {                       // 왼쪽이 정렬돼 있다
            if (a[lo] <= target && target < a[mid]) hi = mid - 1;
            else                                    lo = mid + 1;
        } else {                                     // 오른쪽이 정렬돼 있다
            if (a[mid] < target && target <= a[hi]) lo = mid + 1;
            else                                    hi = mid - 1;
        }
    }

    return -1;
}
```

조건이 네 줄이라 복잡해 보이지만 하는 일은 하나입니다.
**정렬된 반쪽에 답이 있는지 먼저 묻고, 없으면 나머지로 간다.**

위 배열에서 30을 찾으면 이렇게 갑니다.

| 단계 | lo | hi | mid | a[mid] | 판단 |
| --- | --- | --- | --- | --- | --- |
| 1 | 0 | 7 | 3 | 80 | `a[0]=50 <= 80` 이라 왼쪽이 정렬. 30은 50~80 밖이니 오른쪽으로 |
| 2 | 4 | 7 | 5 | 20 | `a[4]=10 <= 20` 이라 왼쪽이 정렬. 30은 10~20 밖이니 오른쪽으로 |
| 3 | 6 | 7 | 6 | 30 | 찾았다 |

## 끊긴 자리 자체를 찾을 때

"가장 오래된 로그가 어디부터인가" 는 배열의 최솟값을 찾는 일이고, 이건 더 간단합니다.

```csharp
int lo = 0, hi = a.Length - 1;

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (a[mid] > a[hi]) lo = mid + 1;   // 끊긴 자리가 오른쪽에 있다
    else                hi = mid;       // 끊긴 자리가 mid 이거나 왼쪽에 있다
}

return lo;   // 최솟값의 자리 = 원래 배열의 시작점
```

**끝 값과 비교한다는 것이 요점입니다.** `a[mid]` 가 마지막 값보다 크다면 그 사이 어딘가에서 끊겼다는 뜻입니다.
`a[lo]` 와 비교하면 회전이 없는 배열에서 답이 어긋나므로 `a[hi]` 쪽을 씁니다.

이 자리를 알면 원래 순서로 읽는 것도 쉬워집니다. 인덱스에 시작점을 더하고 길이로 나눈 나머지를 쓰면 됩니다.

```csharp
int real = (start + i) % a.Length;
```

## 같은 값이 있으면 무너진다

이 방식이 성립하는 이유는 `a[lo] <= a[mid]` 로 **정렬된 쪽을 가려낼 수 있다는 것** 하나입니다.
값이 중복되면 그 판단이 안 됩니다.

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

lo=0, hi=4, mid=2  →  a[lo]=1, a[mid]=1
```

`a[lo] <= a[mid]` 가 성립하니 왼쪽이 정렬됐다고 판단합니다. 그런데 왼쪽은 `[1, 0, 1]` 이라 정렬이 아닙니다.
판단이 틀렸으니 그다음이 전부 틀립니다. 0은 1 이상 1 미만이 아니라서 오른쪽으로 가고,
오른쪽에는 0이 없으니 **못 찾았다고 답합니다.** 배열에 있는데도 그렇습니다.

양 끝과 가운데가 같은 값이면 어느 반쪽에 끊긴 자리가 있는지 구별할 방법이 없습니다.
이럴 때는 한 칸씩 좁히는 수밖에 없고, **최악에는 전부 훑게 되어 `O(n)`** 이 됩니다.

```csharp
if (a[lo] == a[mid] && a[mid] == a[hi]) { lo++; hi--; continue; }
```

중복이 흔한 데이터라면 이 방식 자체를 다시 생각하는 편이 낫습니다.
로그 버퍼라면 시각이 아니라 **순번을 같이 저장해서 중복을 없애는 쪽**이 간단합니다.

## 정리

회전된 정렬 배열은 전체로 보면 정렬이 아니지만, **가운데에서 자르면 반쪽 중 하나는 반드시 정렬돼 있습니다.**
그 반쪽의 양 끝만 보면 찾는 값이 거기 있는지 알 수 있고, 없으면 반대쪽으로 갑니다. 절반을 버리는 것은 그대로입니다.

- 정렬된 쪽인지는 `a[lo] <= a[mid]` 로 가립니다
- 끊긴 자리를 찾을 때는 `a[hi]` 와 비교합니다. `a[lo]` 와 비교하면 회전이 없는 배열에서 틀립니다
- **값이 중복되면 어느 쪽이 정렬인지 못 가리고 최악 `O(n)` 이 됩니다.** 그런 데이터라면 중복을 없앨 방법부터 찾습니다