찾았는데 멈추면 안 되는 이유

랭킹 보드에 점수가 정렬돼 있습니다. 같은 점수를 받은 사람이 여럿인데, 내 등수는 그중 첫 번째 자리여야 합니다. 레벨 10 이상인 유저가 몇 명인지 셀 때도 마찬가지입니다. 레벨 10이 몇 번째 자리에서 시작하는지를 알아야 합니다.

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

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

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

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

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

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

찾고 나서 왼쪽으로 훑으면

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

두 번째 줄이 “첫 번째” 를 만드는 규칙입니다. 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 가 식에 아예 안 들어옵니다.

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

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

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 를 위치가 아니라 확정된 사실로 읽으면 풀립니다.

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

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

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

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    전부 작으니 끝의 다음

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

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

자주 틀리는 세 군데

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

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 입니다.

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

오른쪽을 버리면 계속 왼쪽으로 밀려가 첫 자리에 닿고, 왼쪽을 버리면 오른쪽으로 밀려가 마지막의 다음 자리에 닿습니다. 같은 배열에 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

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

C# 에는 lower_bound 가 없다

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

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 가 되고, 둘을 빼면 개수가 나옵니다