정렬된 배열에서 target 이상인 첫 위치를 찾습니다. 이진 탐색의 경계 오류를 어떻게 피하나요?

이 문제는 target과 같은 원소 하나를 찾는 것이 아니라 target 이상인 첫 위치, 즉 lower bound를 찾는 문제입니다. 먼저 탐색 구간을 [lo, hi)로 정하고, a[mid] < target이면 mid와 왼쪽을 버리며, 그렇지 않으면 mid를 답 후보로 남겨 hi를 줄이겠습니다. 반복이 끝난 lo는 배열 길이일 수도 있으므로 원소가 실제로 있는지 별도로 확인해야 합니다.

반환 경계와 비교자를 검증합니다

다음 구현은 오름차순 배열을 가정합니다.

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

a[mid]가 target보다 작으면 그 위치와 왼쪽에는 답이 없으므로 lo를 오른쪽으로 옮깁니다. 반대로 크거나 같으면 mid 자체가 첫 위치일 수 있으므로 버리지 않고 hi = mid로 좁힙니다. 이처럼 구간 안에 답 후보가 남아 있다는 조건을 반복마다 보존하는 것을 탐색 불변식(search invariant)이라고 부릅니다. 같은 값을 만났다고 즉시 반환하면 더 앞에 중복 값이 있는지 확인하지 못합니다.

경계와 단조 조건을 검증합니다

빈 배열, 모든 값이 target보다 작은 배열, 모든 값이 큰 배열, 중복, 첫 원소·마지막 원소 일치를 테스트하겠습니다. 반환값이 len(a)이면 target 이상인 값이 없다는 뜻일 수 있으므로 idx < len(a)와 a[idx] >= target을 확인한 뒤 사용합니다. target보다 큰 첫 위치를 찾으려면 비교를 a[mid] <= target으로 바꾸되 같은 반열린 구간 규칙을 유지합니다.

이진 탐색은 ‘조건이 한쪽에서는 거짓이고 이후에는 참’처럼 판정이 단조적일 때만 적용할 수 있습니다. 정렬되지 않은 배열이나 중간에 조건이 다시 거짓이 되는 함수에는 경계 코드만 바꿔도 맞지 않습니다. 정수 오버플로가 있는 언어에서는 (lo + hi) // 2 대신 lo + (hi - lo) // 2를 사용하고, 실수 경계는 정확한 종료 조건이나 허용 오차를 정해야 합니다.

검증에서는 선형 스캔을 기준 구현으로 만들어 무작위 배열과 모든 경계 입력의 결과를 비교하겠습니다. 인덱스 반환뿐 아니라 후속 삽입 위치·페이지 커서·중복 정책이 이 경계를 어떻게 해석하는지도 확인해야 합니다.

경계 탐색은 반환값의 의미를 먼저 고정해야 합니다. [0, lo)는 모두 target보다 작고 [hi, n)은 모두 target 이상이라는 불변식을 유지하면 종료 시 lo가 첫 참 위치가 됩니다. 후속 코드가 삽입 위치를 쓰는지 존재 여부를 확인하는지에 따라 len(a) 반환의 의미가 달라집니다.

문자열 정규화·복합 키·대소문자 규칙이 있으면 정렬과 탐색이 같은 비교자를 사용해야 합니다. 기준 구현인 선형 스캔과 무작위 입력을 비교하고, 반복마다 답 후보가 구간에 남는다는 assertion을 둘 수 있습니다. 중복·끝점·빈 배열·오버플로뿐 아니라 정렬 기준 불일치도 테스트하겠습니다.

반열린 접근 구간은 빈 구간을 자연스럽게 표현하고 lo == hi에서 종료하기 쉬워 경계 오류를 줄입니다. 다만 배열이 정렬되어 있다는 사실만으로 비교자의 정렬 순서가 호출마다 안정적이라는 뜻은 아니므로, 로케일·대소문자·NaN 정책을 고정해야 합니다. 복합 키에서는 첫 요소가 같을 때 두 번째와 세 번째 비교까지 같은 규칙으로 수행해야 cursor가 중복되지 않습니다. 구현을 바꿀 때는 경계별 예제와 무작위 기준 비교를 함께 돌려 mid 계산과 후속 인덱스 사용을 분리해서 검증하겠습니다.

정렬 배열 [1,2,2,4]에서 target=2의 lower_bound는 1이고 upper_bound는 3이므로 동등 원소 구간은 [1,3)입니다. 존재하지 않는 3은 두 경계가 모두 3입니다. 이 차이로 중복 개수를 세거나 삽입 위치를 정할 수 있지만, 반환값이 길이 n이면 원소 접근은 하지 않아야 합니다. 경계 탐색과 반환 인덱스의 후속 사용을 별도 테스트로 나누겠습니다.