끝이 어딘지 모르는 배열에서 찾기

서버가 랭킹을 페이지 단위로 내려줍니다. GetScore(rank) 를 부르면 그 등수의 점수가 나오는데, 전체가 몇 명인지는 알려주지 않습니다. 여기서 점수 3000점이 몇 등부터 시작하는지 찾아야 합니다.

로그 파일도 같습니다. 시간순으로 쌓여 있으니 정렬은 돼 있는데, 줄 수는 세어 보기 전에는 모릅니다. 어제 오후 3시의 첫 줄을 찾으려고 파일을 전부 읽는 것은 낭비입니다.

이진 탐색은 구간이 있어야 시작합니다. left 와 right 가 있어야 가운데를 잡을 수 있으니까요. 그러니 구간을 먼저 만들어야 합니다.

오른쪽 끝을 두 배씩 밀어 본다

1번 자리를 봅니다. 찾는 값보다 작으면 2번, 4번, 8번, 16번으로 건너뛰는 폭을 두 배씩 늘립니다. 처음으로 찾는 값 이상인 자리를 만나면 거기가 오른쪽 끝입니다. 왼쪽 끝은 그 직전에 본 자리입니다.

찾는 값 = 3000

GetScore(1)    = 9800   더 간다
GetScore(2)    = 9100   더 간다
GetScore(4)    = 7400   더 간다
GetScore(8)    = 5200   더 간다
GetScore(16)   = 3600   더 간다
GetScore(32)   = 2100   여기서 넘어섰다

→ 구간은 [16, 32]. 이 안에서 이분 탐색

점수는 등수가 커질수록 작아지니 비교 방향만 뒤집으면 되고, 오름차순 배열이면 그대로입니다.

int UnboundedLowerBound(Func<int, int> get, int target) {
    int hi = 1;
    while (get(hi) < target) hi *= 2;      // 넘어설 때까지 두 배로

    int lo = hi / 2;                        // 직전에 본 자리
    while (lo < hi) {                       // 여기서부터는 평범한 이분 탐색
        int mid = lo + (hi - lo) / 2;
        if (get(mid) < target) lo = mid + 1;
        else                   hi = mid;
    }
    return lo;
}

앞의 절반이 구간을 만드는 일이고 뒤의 절반이 그 구간을 좁히는 일입니다. 이렇게 경계를 두 배씩 넓혀 구간을 잡는 방식의 이름이 지수 탐색(exponential search) 입니다. 갤로핑 탐색이라고도 부릅니다. 뒤쪽은 길이를 아는 배열에서 쓰던 것과 한 글자도 다르지 않습니다.

비용은 전체 크기가 아니라 답의 위치에 달렸다

두 단계 모두 두 배씩 움직입니다.

합쳐서 2 log p, 즉 O(log p) 입니다. 전체가 100만이든 1억이든 상관없습니다. 답이 32등 근처에 있다면 열 번 남짓이면 끝납니다. 데이터가 얼마나 큰지 몰라도 되는 이유가 이것입니다.

배열 길이를 아는 경우와 비교하면 차이가 분명합니다. 길이가 1억이면 그냥 이분 탐색은 처음부터 1억을 반으로 자르며 시작해서 스물일곱 번쯤 걸립니다. 답이 앞쪽에 있어도 마찬가지입니다. 경계를 넓히는 방식은 답이 앞에 있으면 앞에서 끝납니다.

왜 하필 두 배인가

한 칸씩 밀면 p 번이라 훑는 것과 같습니다. 그럼 열 배씩 밀면 더 빠를까요.

넓힐 때 아낀 만큼 좁힐 때 더 냅니다. 마지막 구간의 크기가 배수만큼 커지기 때문입니다. 두 배가 이 둘의 균형이 맞는 지점이고, 구현도 hi *= 2 한 줄이라 가장 단순합니다.

끝을 넘어가면 무슨 일이 생기나

경계를 넓히다 보면 없는 자리를 부르게 됩니다. 이 처리를 안 정하면 여기서 터집니다. 데이터를 주는 쪽이 어떻게 반응하는지 먼저 확인해야 합니다.

센티넬 쪽이 코드가 깔끔합니다. 없는 자리를 int.MaxValue 로 보면 비교식을 고칠 필요가 없습니다.

int Get(int i) => i < Count ? data[i] : int.MaxValue;

호출 하나가 네트워크 왕복이라면 계산 횟수보다 호출 횟수가 비용입니다. 그럴 때는 한 번에 여러 칸을 받아 두고(페이지 단위) 그 안에서는 메모리로 비교하는 편이 낫습니다. 알고리즘은 그대로 두고 Get 만 캐시를 두른 것으로 바꾸면 됩니다.

길이를 아는 배열에는 쓰지 않는다

이 방법이 필요한 이유는 구간이 없어서입니다. a.Length 를 알고 있으면 구간은 이미 있습니다. 거기서 경계를 넓히는 단계를 붙이면 하는 일 없이 비교만 늘어납니다.

헷갈리기 쉬운 자리라 조건을 정리하면 이렇습니다.

• 길이를 안다 → 처음부터 [0, Length) 로 이분 탐색
• 길이를 모른다 → 경계를 두 배씩 넓혀 구간을 만든 뒤 이분 탐색
• 길이는 아는데 답이 앞쪽에 몰려 있다 → 여전히 그냥 이분 탐색. 앞쪽이라는 것을 알면 right 를 작게 잡으면 됩니다

정리

끝을 모르는 정렬 데이터에서 찾는 일은 두 단계입니다. 구간을 만들고, 그 구간을 좁힙니다.

• 오른쪽 끝을 두 배씩 밀어 처음으로 찾는 값을 넘어서는 자리를 잡습니다. 왼쪽 끝은 그 직전 자리입니다
• 그다음은 평범한 이분 탐색입니다. 앞 단계가 만들어 준 구간을 쓸 뿐입니다
• 비용은 O(log p) 이고 p 는 답의 위치입니다. 전체 크기를 몰라도 되고, 알 필요도 없습니다

없는 자리를 부르는 순간을 어떻게 다룰지 먼저 정하세요. 예외냐 센티넬이냐에 따라 루프의 모양이 달라집니다.