이분탐색 알고리즘 (Binary Search)

 

이분탐색?

이분 탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾는 효율적인 알고리즘입니다.

배열을 절반씩 나누어 탐색하기 때문에 시간 복잡도는 O(log n)입니다.

---

알고리즘 설명

1. 정렬된 배열에서 중간 인덱스를 선택합니다.
2. 찾고자 하는 값(target)과 중간 값(mid) 값을 비교합니다.
   • 만약 target이 중간 값보다 작다면, 왼쪽 절반만 탐색합니다.
   • 만약 target이 중간 값보다 크다면, 오른쪽 절반만 탐색합니다.
3. 이 과정을 반복하여 찾고자 하는 값이 중간 값과 같아질 때까지 배열을 절반으로 나누어 탐색합니다.

---

구현 코드

1. 재귀 방식

def binary_search(arr, target, low, high):
    if low > high:
        return -1  # 값을 찾지 못한 경우

    mid = (low + high) // 2

    # target을 찾은 경우
    if arr[mid] == target:
        return mid
        
    # target이 중간 값보다 작은 경우 왼쪽 절반 탐색
    elif arr[mid] > target:
        return binary_search(arr, target, low, mid - 1)
        
    # target이 중간 값보다 큰 경우 오른쪽 절반 탐색
    else:
        return binary_search(arr, target, mid + 1, high)

 

2. 반복문 방식

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

    while low <= high:
        mid = (low + high) // 2

        # target을 찾은 경우
        if arr[mid] == target:
            return mid
        
        # target이 중간 값보다 작은 경우 왼쪽 절반 탐색
        elif arr[mid] > target:
            high = mid - 1
        
        # target이 중간 값보다 큰 경우 오른쪽 절반 탐색
        else:
            low = mid + 1

    return -1  # 값을 찾지 못한 경우

 

3. 내장 함수 사용

파이썬의 bisect 모듈을 사용하면 이분 탐색을 간단하게 구현할 수 있습니다. 

• bisect_left(arr, target) = 정렬된 순서를 유지하면서 리스트 arr에 target을 삽입할 가장 왼쪽 인덱스를 찾는 메소드
• bisect_right(arr, target) = 정렬된 순서를 유지하도록 리스트 arr에 target을 삽입할 가장 오른쪽 인덱스를 찾는 메소드

import bisect

def binary_search(arr, target):
    index = bisect.bisect_left(arr, target)
    
    # 배열 범위 내에 있고 해당 위치의 값이 target과 같으면 인덱스 반환
    if index < len(arr) and arr[index] == target:
        return index
    else:
        return -1  # target이 배열에 없는 경우