LeetCode 704 Binary Search 풀이: 정렬 배열 이분 탐색

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

• 문제: 704. Binary Search
• 출처: LeetCode
• 자체 판단 난이도: Level 2

정렬된 배열의 중간값을 기준으로 탐색 구간을 절반씩 줄이는 문제다. 구현은 간단하지만 닫힌 구간의 경계와 갱신 조건을 정확히 잡아야 하므로 Level 2로 판단했다.

1. 문제 요약

오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어진다. 배열에 target이 있으면 해당 인덱스를 반환하고, 없으면 -1을 반환해야 한다.

배열의 원소는 중복되지 않으며, 배열 길이는 1 이상 10^4 이하다. 목표 시간 복잡도는 O(log n)이므로 배열을 처음부터 끝까지 확인하는 선형 탐색은 사용할 수 없다.

예를 들어 [-1, 0, 3, 5, 9, 12]에서 9를 찾으면 인덱스 4를 반환하고, 2를 찾으면 배열에 존재하지 않으므로 -1을 반환한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

판정 함수와 탐색 구간

이 문제는 배열이 정렬되어 있으므로 중간값과 target의 대소를 비교해 탐색 구간을 정할 수 있다. 닫힌 구간 [left, right]를 현재 확인할 후보 범위로 정의한다.

중간 인덱스는 다음과 같이 계산한다.

mid = left + (right - left) // 2

중간값에 따라 다음처럼 구간을 줄인다.

• nums[mid] == target: 목표값을 찾았으므로 mid를 반환한다.
• nums[mid] < target: 정렬 순서상 mid와 그 왼쪽에는 목표값이 없다. left = mid + 1로 갱신한다.
• nums[mid] > target: mid와 그 오른쪽에는 목표값이 없다. right = mid - 1로 갱신한다.

반복문이 끝났다는 것은 모든 후보를 제외했다는 뜻이므로 -1을 반환한다.

정렬 조건이 후보 절반을 보장하는 이유

현재 구간의 중간값이 목표값보다 작다면, 정렬된 배열의 왼쪽 부분 전체도 목표값보다 작다. 반대로 중간값이 목표값보다 크다면 오른쪽 부분 전체를 제외할 수 있다. 오름차순이라는 조건 덕분에 매번 탐색 범위의 절반을 안전하게 버릴 수 있다.

탐색 구간을 닫힌 구간 [left, right]로 정했으므로 중간값을 후보에서 제외할 때는 mid + 1 또는 mid - 1로 경계를 갱신한다. 그래야 구간이 줄어들고 무한 반복도 피할 수 있다.

예제 배열 [-1, 0, 3, 5, 9, 12]에서 target = 9를 찾는 동안 구간은 다음처럼 바뀐다.

첫 비교에서 인덱스 0~2를 버려도 9는 남은 구간에 있다. 이처럼 갱신마다 정답 후보를 보존하는 것이 닫힌 구간 이분 탐색의 핵심 불변식이다.

오답 접근과 반례

배열을 왼쪽부터 순서대로 확인하는 선형 탐색은 결과는 구할 수 있지만 O(n) 시간이 필요하다. nums = [0, 1, 2, ..., 9999], target = 9999처럼 목표값이 마지막에 있으면 거의 모든 원소를 확인해야 하므로 문제의 O(log n) 조건을 만족하지 못한다.

left = mid처럼 중간값을 제외하지 않는 갱신도 잘못된 구간 처리다. 후보가 두 개 남아 left = 0, right = 1, mid = 0인 상황에서 left = mid를 수행하면 경계가 변하지 않아 반복이 끝나지 않을 수 있다. 현재 중간값이 목표가 아니라는 사실을 이용해 항상 mid + 1 또는 mid - 1로 갱신해야 한다.

시간·공간 복잡도

반복할 때마다 탐색 구간의 크기가 절반 정도로 줄어들므로 시간 복잡도는 O(log n)이다. 배열 외에 경계와 중간 인덱스만 저장하므로 공간 복잡도는 O(1)이다.

3. 문제 해결 코드 (Python)

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left = 0
        right = len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1

right를 len(nums) - 1로 초기화해 마지막 원소까지 닫힌 구간에 포함한다. 목표값을 찾지 못하면 경계를 줄이다가 left가 right보다 커진다. 이때 후보 구간이 비었으므로 -1을 반환한다.

중간 인덱스는 left + (right - left) // 2로 계산한다. Python에서는 정수 오버플로가 발생하지 않지만, 고정 크기 정수를 쓰는 언어에서도 안전한 형태다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 공식 예제와 단일 원소 경계를 재현할 수 있다.

solver = Solution()
assert solver.search([-1, 0, 3, 5, 9, 12], 9) == 4
assert solver.search([-1, 0, 3, 5, 9, 12], 2) == -1
assert solver.search([5], 5) == 0

4. 공식 예제와 추가 검증

공식 예제와 배열 하나, 양끝 원소, 큰 정렬 배열을 포함한 케이스를 Python 코드로 실행해 확인했다.

공식 예제

추가 검증 1: 원소가 하나인 배열

입력: nums = [5], target = 5
기대 출력: 0
확인 결과: 통과
검증 목적: 시작과 끝 경계가 같은 최소 배열에서 목표값을 찾는지 확인

추가 검증 2: 원소가 하나지만 목표값이 없는 경우

입력: nums = [5], target = -5
기대 출력: -1
확인 결과: 통과
검증 목적: 한 번의 비교 후 빈 탐색 구간을 처리하는지 확인

추가 검증 3: 배열의 양끝 원소

입력: nums = [-10, -5, -1, 0, 4], target = -10
기대 출력: 0
확인 결과: 통과

입력: nums = [-10, -5, -1, 0, 4], target = 4
기대 출력: 4
확인 결과: 통과
검증 목적: 왼쪽 끝과 오른쪽 끝을 각각 목표값으로 탐색하는지 확인

추가 검증 4: 큰 정렬 배열에서 마지막 값

입력: nums = [-10000, -9998, ..., 9998], target = 9998
기대 출력: 9999
확인 결과: 통과
검증 목적: 탐색 구간을 반복해서 줄여 마지막 원소를 찾는지 확인

5. 다른 풀이 방식 검색 및 비교

• LeetCode 공식 문제는 오름차순 정렬과 O(log n) 시간 제한, 목표값의 인덱스 반환 조건을 정의한다.
• NeetCode의 Binary Search 설명은 반복형과 재귀형 이분 탐색을 비교하고, 중간 인덱스와 양끝 경계를 이용해 탐색 범위를 줄이는 접근을 설명한다.

재귀형 구현도 매 호출에서 왼쪽 또는 오른쪽 절반만 남기므로 O(log n) 시간에 동작한다. 다만 재귀 호출 스택에 O(log n) 공간이 필요하다. 이 글에서는 반복문으로 같은 탐색을 구현해 추가 공간을 O(1)로 유지했다. Python의 bisect 모듈을 사용할 수도 있지만, 이 문제는 이분 탐색의 경계와 종료 조건을 직접 구현하는 것을 확인하는 문제이므로 라이브러리 호출 없이 작성했다.

마무리

Binary Search는 정렬된 배열에서 중간값과의 비교 결과로 절반의 후보를 버리는 알고리즘이다. 닫힌 탐색 구간 [left, right]의 의미를 정하고, 중간값을 제외할 때 +1과 -1을 적용하면 경계 오류와 무한 반복을 피할 수 있다. 이 구현은 O(log n) 시간과 O(1) 공간으로 목표값의 인덱스를 반환한다.