반열린 구간으로 첫 이진 탐색 만들기

순차 탐색은 모든 값을 볼 수 있습니다. 오름차순으로 정렬된 자료라면 중간값보다 작은 쪽과 큰 쪽을 구분해 후보를 줄일 수 있습니다. 목표는 단순히 목표를 한 번 찾는 것이 아니라 중복 목표의 첫 위치를 안정적으로 찾는 것입니다. 인덱스·반열린 범위·불변조건을 복습하세요.

개념과 약속

입력은 비교 가능한 값들의 오름차순 리스트와 목표입니다. 반환값은 첫 인덱스이며 없으면 -1입니다. 정렬되지 않은 입력에는 정확성을 보장하지 않습니다. lo는 포함하는 왼쪽 경계, hi는 포함하지 않는 오른쪽 경계입니다. 후보 구간 [lo, hi)의 칸 수는 hi-lo입니다. 처음에는 lo=0, hi=len(values)입니다.

중간 위치 mid=(lo+hi)//2에서 값이 목표보다 작으면 mid까지의 원소는 첫 목표일 수 없어 lo=mid+1입니다. 그렇지 않으면 mid가 목표일 수도 있으므로 버리지 않고 hi=mid로 둡니다. 값이 같아도 즉시 반환하지 않는 이유가 중복의 첫 위치라는 명세에 있습니다. 멈춘 뒤에는 그 위치가 범위 안이고 실제로 같은지 다시 확인합니다.

손으로 상태 추적하기

목표 4, 목록 [2,4,4,7,9]를 사용합니다.

hi=2로 줄일 때 인덱스 2는 다음 검사 구간에서 빠지지만, 답이 될 수 있는 경계 위치로 남습니다. 왼쪽에 더 이른 4가 없는지 찾는 과정입니다.

직접 실행하기

아래 코드는 이 본문만으로 실행할 수 있습니다. lesson.py로 저장하고 첫 장에서 확인한 Python 명령으로 실행하세요.

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


values = [2, 4, 4, 7, 9]
print(binary_search_first(values, 4))
print(binary_search_first(values, 6))
print(binary_search_first([], 4))
print(binary_search_first([4, 4], 4))

실행 결과:

1
-1
-1
0

왜 맞고 언제 끝나는가

반복 중 lo보다 왼쪽의 값은 목표보다 작고, hi부터 오른쪽의 값은 목표 이상입니다. 정렬된 순서 덕분에 중간값 비교로 이 사실을 갱신할 수 있습니다. 처음에는 양쪽 바깥 범위가 비어 있어 성립합니다. 종료 시 lo=hi는 목표 이상의 값이 처음 나타날 수 있는 경계입니다. 그 값이 목표와 같은지 확인하면 첫 일치 또는 없음이 결정됩니다.

lo < hi일 때 lo ≤ mid < hi입니다. 왼쪽을 갱신하면 lo가 최소 1 증가하고, 오른쪽을 갱신하면 hi가 감소합니다. hi-lo가 음수가 되지 않으면서 엄격히 줄어 종료합니다. 빈 목록은 반복 없이 길이 검사에서 -1을 반환합니다.

비용과 적용 범위

후보를 거의 절반씩 줄여 비교 횟수는 O(log n), 추가 공간은 O(1)입니다. 이미 정렬된 자료라는 전제가 필요합니다. 매번 정렬부터 하면 정렬 비용도 포함해야 하며, 미정렬 목록에서 목표를 한 번만 찾는다면 순차 탐색이 더 간단할 수 있습니다.

스스로 풀어 보기

1. [1,3,3,3,8,10]에서 목표 3과 9에 대해 lo·hi·mid를 끝까지 추적하세요.
2. lo=mid+1을 lo=mid로 바꾸면 길이 1인 목록에서 어떤 종료 문제가 생기나요?
3. [9,1,7]에 이 코드를 적용해 원하는 답이 우연히 나왔다면 정렬 전제를 제거해도 되나요?

힌트

1. 목표가 없을 때에도 경계는 찾고 마지막 같음 검사가 실패합니다.
2. lo=0, hi=1에서 mid=0입니다.
3. 사례 성공과 일반적인 불변조건을 구분하세요.

해설

1. 목표 3은 (0,6,3)→(0,3,1)→(0,1,0)→(1,1)이라 인덱스 1입니다. 목표 9는 (0,6,3)→(4,6,5)→(4,5,4)→(5,5)이고 인덱스 5의 값 10이 달라 -1입니다.
2. 값이 목표보다 작으면 lo가 0에 머물고 같은 비교를 끝없이 합니다. 버린 칸을 경계에서도 제외해야 합니다.
3. 안 됩니다. 중간값의 한쪽에 있는 모든 값에 관한 추론이 정렬 없이는 성립하지 않습니다.

흔한 오해

같음을 발견하자마자 반환하면 아무 일치 위치를 찾는 알고리즘이 됩니다. 또 hi=len(values)-1로만 바꾸면 닫힌 구간과 반열린 구간의 규칙을 섞게 됩니다. 경계 표현과 갱신식을 함께 설계하세요.

복습과 다음 연결

정렬 전제를 만들려면 기본 정렬로 진행하세요. 복습은 정확성과 연결합니다. Python의 같은 경계 개념은 공식 bisect에서 비교해 볼 수 있습니다.