이진 탐색과 경계 불변식

정렬된 데이터에서 “값이 있는가”만 묻는 것과 “조건이 처음 참이 되는 위치”를 반환하는 것은 다른 API입니다. 이 차이를 먼저 고정하면 중복 값, 삽입 위치, 값이 없는 경우를 각각 예외 처리하지 않고 하나의 경계 규칙으로 설명할 수 있습니다. 이후의 구현은 답을 찾는 즉시 반환하는 방식이 아니라, 답이 있을 수 있는 반열린 구간을 끝까지 줄이는 방식입니다.

값 검색과 첫 참 위치

정렬 배열에서 target을 찾는 문제는 target 이상인 첫 위치를 찾고 그 값이 target인지 확인하는 문제로 표현할 수 있습니다. 이 경계가 lower_bound입니다. 값이 없으면 삽입 위치를 반환하고, 모든 값이 작으면 배열 길이 n을 반환합니다.

더 일반적으로는 false, false, …, true, true처럼 한 번만 바뀌는 단조 조건의 첫 참 위치를 찾습니다. 조건이 중간에 다시 거짓이 되면 이 알고리즘을 적용할 수 없습니다.

구현과 불변식

def lower_bound(a, target):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

반복마다 [0, lo)의 값은 모두 target보다 작고 [hi, n)의 값은 모두 target 이상입니다. 원소를 읽는 미확정 구간은 [lo, hi)입니다. 답으로 반환할 경계는 n을 포함할 수 있으므로 배열 접근 가능한 인덱스와 경계 후보를 혼동하면 안 됩니다.

• a[mid] < target이면 mid까지 답이 아니므로 lo = mid + 1입니다.
• 아니면 mid가 답일 수 있으므로 hi = mid입니다.
• 매번 구간이 줄어들고 lo == hi이면 그 위치가 첫 참 경계입니다.

예제별 경계 비교

배열 [1, 2, 2, 4]에서 다음과 같습니다.

target	lower_bound	upper_bound	동등 구간
2	1	3	[1,3)
3	3	3	빈 구간
5	4	4	빈 구간, 끝 삽입 위치

upper_bound는 target보다 큰 첫 위치를 찾습니다. a[mid] <= target이면 mid까지는 답이 될 수 없으므로 lo = mid + 1로 옮기고, 그렇지 않으면 mid를 후보로 남겨 hi = mid로 줄입니다. 예제에서 target=2이면 lower_bound=1, upper_bound=3이어서 [1,3)에 같은 값이 두 개 있다는 것을 3-1=2로 계산할 수 있습니다. 두 경계 모두 반열린 구간 불변식을 그대로 유지하므로, 같은 값의 개수와 삽입 위치를 한 규칙으로 다룰 수 있습니다.

target 2의 세 번의 판단

같은 배열에서 lower_bound(a, 2)를 실행해 보겠습니다. 시작 범위는 [0, 4)이고, 여기서 4는 마지막 원소의 인덱스가 아니라 배열 끝 경계입니다.

반복 전 lo·hi	mid와 값	판단	다음 lo·hi
0·4	mid=2, 값=2	2 이상이므로 mid가 첫 위치일 수도 있음	0·2
0·2	mid=1, 값=2	아직 왼쪽에 같은 값이 있을 수도 있음	0·1
0·1	mid=0, 값=1	1은 target보다 작으므로 0은 제외	1·1

마지막에는 읽을 미확정 원소가 남지 않고 lo=hi=1이 됩니다. 첫 반복에서 값 2를 찾았다고 즉시 반환했다면 인덱스 2를 돌려주어 첫 번째 2라는 요구를 놓쳤을 것입니다. 같은 값이 있는지 찾는 문제와 그 값의 첫 위치를 찾는 문제가 다른 지점입니다.

그림을 글로 읽기

• [0, 4): 1 · 2 · 2 · 4 · mid 2의 값이 2 → hi=2
• [0, 2): 1 · 2 · mid 1의 값이 2 → hi=1
• [0, 1): 1 · mid 0의 값이 1 → lo=1
• lo = hi = 1: 첫 2의 위치 반환

1. [0, 4) → [0, 2): 오른쪽 축소
2. [0, 2) → [0, 1): 오른쪽 축소
3. [0, 1) → lo = hi = 1: 왼쪽 제외

종료 조건과 숫자 범위

시간은 O(log n), 보조 공간은 반복 구현에서 O(1)입니다. lo + (hi-lo)//2는 lo+hi의 overflow를 피하지만 hi-lo가 표현 가능하다는 전제가 필요합니다. Python 정수는 자동 확장되지만 고정 폭 정수 언어는 전체 탐색 범위와 signed·unsigned 혼합을 확인해야 합니다.

실수 탐색에서는 중간값이 반올림으로 끝점과 같아질 수 있습니다. 허용 오차·반복 상한·정체 감지를 정하고, 숫자 오차를 무시한 lo != hi 종료에 의존하지 않습니다.

다른 문제 적용 조건

• 정렬 문자열: 저장과 탐색에서 같은 정규화·대소문자·collation을 사용합니다.
• 복합 키: 첫 값이 같을 때 보조 키까지 같은 비교 순서를 적용합니다.
• 누적 가중치: 가중치가 비음수여야 누적값이 단조라는 전제가 유지됩니다.
• 시간·용량의 정답 탐색: 판정 함수가 실제로 단조인지 증명해야 합니다. 비싼 판정 함수의 비용도 전체 시간에 곱해집니다.

예를 들어 target=2에서 첫 번째로 2를 만났다고 즉시 반환하면 결과는 맞을 때도 있지만 lower_bound 계약은 깨집니다. 빈 배열에서 반환된 n을 읽어 생기는 범위 오류와, 길이 1 구간에서 lo=mid가 반복되는 정체를 서로 다른 증상으로 기록하면 어느 경계 규칙이 깨졌는지 역추적할 수 있습니다.

반열린 구간 구현의 흔한 실패

반환값 n을 바로 a[n]으로 읽거나, hi=mid-1 규칙을 반열린 코드에 섞거나, lo=mid로 바꾸어 길이 1 구간에서 정체하는 오류가 흔합니다. 한 가지 구간 표현을 정해 끝까지 유지하는 것이 중요합니다.

경계 조건·불변식 연습

1. 빈 배열과 target이 양끝 밖인 경우를 손으로 실행합니다.
2. 선형 스캔과 무작위 배열의 결과를 비교합니다.
3. 매 반복에 불변식을 assertion으로 확인합니다.
4. 정렬 기준을 바꾸었을 때 탐색 비교도 함께 바꾸지 않으면 실패하는 사례를 만듭니다.