[알고리즘] 파이썬으로 이진 탐색(Binary Search) 구현하기

이진 탐색(혹은 이분 탐색)은 정렬된 배열에서 특정한 값을 찾는 알고리즘이다. 탐색 범위를 절반씩 줄여가며 빠르게 원하는 값을 찾아낼 수 있어 효율적이다. 이진 탐색의 기본적인 원리는 다음과 같다.

1. 이분 탐색을 위해 오름차순 또는 내림차순으로 정렬된 배열을 준비
2. 탐색 범위의 중간에 있는 값을 찾아서, 찾고자 하는 값과 비교
3. 비교에서 범위를 좁힌다. (오름차순 기준)
   3-1. 중간값이 찾고자 하는 값보다 크면 탐색 범위를 왼쪽 절반으로 좁힌다.
   3-2. 중간값이 찾고자 하는 값보다 작으면 탐색 범위를 오른쪽 절반으로 좁힌다.
4. 3의 과정을 원하는 값을 찾을 때까지 반복

위 과정을 하나의 함수로 정리하면 다음과 같다.

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

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

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

    return -1  # 존재하지 않는 경우