알고리즘 이진 탐색(Binary Search) 파이썬 예제

이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾는 알고리즘입니다. 이 알고리즘은 배열을 반으로 나누어 찾고자 하는 값과 비교하면서 탐색 범위를 반으로 줄여가는 방식으로 동작합니다.

예를 들어, 오름차순으로 정렬된 다음과 같은 배열이 있다고 가정해봅시다.

[1, 3, 5, 7, 9, 11, 13, 15]

이 배열에서 7을 찾는다면, 배열의 중간 값인 9와 비교하여 7이 9보다 작기 때문에 7이 존재할 수 있는 왼쪽 배열 `[1, 3, 5, 7]`에서 이진 탐색을 다시 수행합니다. 이번에는 왼쪽 배열의 중간 값인 3과 비교하여 7이 3보다 크기 때문에 오른쪽 배열 `[5, 7]`에서 이진 탐색을 다시 수행합니다. 이번에는 오른쪽 배열의 중간 값인 7이 7과 일치하기 때문에 7을 찾았습니다.

이진 탐색의 시간 복잡도는 O(log n)입니다. 따라서, 배열의 크기가 매우 큰 경우에도 효율적으로 탐색이 가능합니다.

다음은 Python으로 구현한 이진 탐색의 예제입니다.

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

이 함수는 정렬된 배열 `arr`과 찾고자 하는 값 `target`을 입력받아, `target`이 존재하는 인덱스를 반환하거나, `target`이 존재하지 않을 경우 -1을 반환합니다. 이진 탐색 알고리즘의 핵심인 `left`, `right`, `mid` 변수를 이용하여 탐색 범위를 좁혀가는 방식으로 동작합니다.