한 바퀴 돌아간 배열에서도 반쪽은 정렬돼 있다

최근 로그 1,000줄을 링 버퍼에 담아 둡니다. 꽉 차면 가장 오래된 줄부터 덮어쓰니, 배열 어딘가에서 시간이 한 번 끊깁니다.

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

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

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

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

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

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

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을 찾으면 이렇게 갑니다.

끊긴 자리 자체를 찾을 때

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

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] 쪽을 씁니다.

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

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) 이 됩니다.

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

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

정리

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

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