이진 탐색의 기본 원리

이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 효율적으로 찾는 대표적인 알고리즘입니다. 탐색 과정은 배열의 중앙 요소부터 시작하며, 이 값이 목표값과 일치하면 탐색을 종료합니다. 만약 목표값이 중앙값보다 크다면 오른쪽 반쪽에서, 작다면 왼쪽 반쪽에서 계속 탐색을 진행합니다. 이 방식은 매번 탐색 범위를 절반으로 줄이기 때문에 매우 빠릅니다.

시간 및 공간 복잡도

배열의 길이를 n이라고 할 때, 각 단계마다 남은 후보 수가 절반으로 줄어들므로 최대 log₂(n) 번의 비교만 수행하면 됩니다. 따라서 시간 복잡도는 O(log n)이며, 공간 복잡도는 두 개의 인덱스 변수만 사용하므로 O(1)입니다.

제약 조건

• 데이터가 반드시 정렬되어 있어야 합니다. 비정렬 데이터는 사전에 정렬해야 하는데, 이 과정의 비용(O(n log n))이 오히려 순차 탐색보다 클 수 있습니다.
• 배열 기반 자료구조에서만 효율적으로 작동하며, 연결 리스트에서는 인덱스 접근이 느려 적용하기 어렵습니다.
• 작은 데이터셋에서는 간단한 선형 탐색이 더 빠를 수 있습니다. 이진 탐색은 계산 오버헤드가 존재하기 때문입니다.

기본 구현: 삽입 위치 찾기

정렬된 배열에서 주어진 값의 위치를 찾거나, 존재하지 않을 경우 삽입될 위치를 반환하는 문제입니다. LeetCode 35번 문제와 동일한 요구사항을 충족합니다.

def find_insert_position(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return left

2차원 행렬 탐색

행과 열이 모두 정렬된 2D 매트릭스에서 특정 값을 찾는 문제입니다. 각 행의 첫 번째 원소가 이전 행의 마지막 원소보다 크다는 조건 덕분에 전체 구조가 일종의 일차원 정렬 배열처럼 다뤄질 수 있습니다.

def search_2d_matrix(matrix, target):
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    low, high = 0, rows * cols - 1

    while low <= high:
        mid = low + (high - low) // 2
        row_idx = mid // cols
        col_idx = mid % cols
        current = matrix[row_idx][col_idx]

        if current == target:
            return True
        elif current < target:
            low = mid + 1
        else:
            high = mid - 1

    return False

범위 탐색: 첫 번째와 마지막 위치 찾기

중복된 값이 있을 때, 목표값의 시작 인덱스와 끝 인덱스를 모두 찾아야 하는 상황입니다. 단순히 한 번 찾은 후 양쪽으로 확장하는 방법은 최악의 경우 O(n)이 될 수 있지만, 여기서는 각 경계를 개별적으로 이진 탐색으로 찾는 방식을 제안합니다.

def find_first_last_position(nums, target):
    def find_bound(is_first):
        left, right = 0, len(nums) - 1
        bound = -1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                bound = mid
                if is_first:
                    right = mid - 1
                else:
                    left = mid + 1
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return bound

    first = find_bound(True)
    if first == -1:
        return [-1, -1]
    last = find_bound(False)
    return [first, last]

회전된 배열에서 탐색

정렬된 배열이 어느 지점에서 회전된 상태일 때, 여전히 O(log n) 시간 내에 탐색을 수행해야 합니다. 핵심 아이디어는 매번 분할했을 때 두 부분 중 하나는 반드시 정렬되어 있다는 점을 이용하는 것입니다.

def search_in_rotated_array(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid

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

회전 배열의 최솟값 찾기

회전된 정렬 배열에서 가장 작은 원소를 찾는 문제입니다. 마찬가지로 이진 탐색을 활용하며, 중간값과 오른쪽 끝값을 비교하여 최솟값이 포함된 반쪽을 결정합니다.

def find_minimum_in_rotated(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            right = mid
    return nums[left]

피크 원소 찾기

양 옆보다 큰 값을 갖는 "피크"를 찾는 문제입니다. 가상의 무한대(-∞)가 양 끝에 있다고 가정하므로, 배열 내에는 반드시 하나 이상의 피크가 존재합니다. 기울기를 판단하여 탐색 방향을 결정합니다.

def find_peak_element(nums):
    if len(nums) == 1:
        return 0

    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        
        left_val = float('-inf') if mid == 0 else nums[mid - 1]
        right_val = float('-inf') if mid == len(nums) - 1 else nums[mid + 1]

        if nums[mid] > left_val and nums[mid] > right_val:
            return mid
        elif nums[mid] < right_val:
            left = mid + 1
        else:
            right = mid - 1
    return -1