Binary Search

이번에 알아볼 것은 이분 탐색(Binary Search)이다.
이분탐색이 뭘까?

이분 탐색이란?

정렬된 배열에서 특정 값을 빠르게 찾기 위해 사용하는 알고리즘.
배열을 반으로 나누면서 원하는 값을 좁혀 나가는 방식.
이 방식은 선형 탐색(linear search) 처럼 처음부터 끝까지 하나하나 확인하는 게 아니라,
한 번 비교할 때마다 탐색 범위가 반으로 줄어들어 매우 빠름

🕐 시간 복잡도

• 선형 탐색 : O(n)
• 이분 탐색 : O(log₂ n)

.
.
.
.

이분 탐색을 하려면 반드시 있어야 하는 조건이 있다 !

1. 데이터가 정렬되어 있어야 함(오름차순 or 내림차순)

2. 인덱스로 접근 가능한 자료구조여야 함 (ex: 배열)

👣 동작 방식 (오름차순 정렬 기준)

배열에서 값 x를 찾고 싶다고 하자.
1. 시작점 = low, 끝점 = high

2. 중간점 mid = (low + high) // 2
   
   
3. A[mid]와 x를 비교

• A[mid] == x → 정답
• A[mid] < x → 정답은 오른쪽에 있음 → low = mid + 1
• A[mid] > x → 정답은 왼쪽에 있음 → high = mid - 1
  

4.이 과정을 low > high 될 때까지 반복

언제 쓰는가 ?

• 정렬된 배열이나 리스트에서 값 찾을 때

• Lower bound, Upper bound 찾을 때 (특정 조건을 만족하는 가장 작은/큰 인덱스)

• 매개변수 탐색(Parametric Search): 정답이 될 수 있는 값이 범위 내에 있을 때 → 이분 탐색으로 범위를 줄여가며 해 찾기

예제 코드

반복문 방식

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid  # 인덱스를 반환
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # 못 찾은 경우

재귀(recursive) 방식

def binary_search_recursive(arr, target, low, high):
    if low > high:
        return -1

    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, high)
    else:
        return binary_search_recursive(arr, target, low, mid - 1)