파이썬으로 구현하는 이진 탐색(Binary Search) 프로그램

이 글에서는 주어진 문제를 해결하기 위한 접근 방식과 실제 구현 방법을 단계별로 살펴봅니다.

문제 정의 — 정렬된 리스트가 하나 주어지며, 이진 탐색(Binary Search) 기법을 활용해 원하는 요소의 위치를 찾아야 합니다.

알고리즘 개요

• 찾으려는 값 x를 배열의 중간 요소와 비교합니다.
• x가 중간 요소와 일치하면 해당 인덱스(mid)를 반환합니다.
• x가 중간 요소보다 크다면, x는 반드시 중간 요소 뒤쪽(오른쪽 절반)에 존재합니다. 따라서 오른쪽 절반을 대상으로 다시 탐색을 진행합니다.
• x가 중간 요소보다 작다면, 왼쪽 절반을 대상으로 다시 탐색을 진행합니다.

매 단계마다 탐색 범위가 절반으로 줄어들기 때문에, 이진 탐색의 시간 복잡도는 O(log n)으로 매우 효율적입니다. 단, 이 방법은 데이터가 반드시 정렬되어 있어야 한다는 전제 조건이 필요합니다.

방법 1: 재귀(Recursion)를 이용한 구현

함수가 자기 자신을 호출하면서 탐색 범위를 절반씩 좁혀 나가는 방식입니다.

def binary_search_recursive(arr, start, end, x):
    # 종료 조건 확인
    if end >= start:
        mid = start + (end - start) // 2

        # 요소가 정확히 중간에 있는 경우
        if arr[mid] == x:
            return mid

        # 요소가 중간값보다 작은 경우 → 왼쪽 절반 탐색
        elif arr[mid] > x:
            return binary_search_recursive(arr, start, mid - 1, x)

        # 요소가 중간값보다 큰 경우 → 오른쪽 절반 탐색
        else:
            return binary_search_recursive(arr, mid + 1, end, x)
    else:
        # 배열에서 요소를 찾지 못한 경우
        return -1

arr = sorted(['t', 'u', 't', 'o', 'r', 'i', 'a', 'l'])
x = 'r'
result = binary_search_recursive(arr, 0, len(arr) - 1, x)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Element is not present in array")

방법 2: 반복문(Iteration)을 이용한 구현

while 루프를 사용해 재귀 호출 없이 동일한 로직을 구현할 수 있습니다. 함수 호출 오버헤드가 없어 대용량 데이터에서 유리합니다.

def binary_search_iterative(arr, x):
    start = 0
    end = len(arr) - 1

    while start <= end:
        mid = start + (end - start) // 2

        # 요소가 정확히 중간에 있는 경우
        if arr[mid] == x:
            return mid

        # 요소가 중간값보다 작은 경우 → 왼쪽 절반 탐색
        elif arr[mid] > x:
            end = mid - 1

        # 요소가 중간값보다 큰 경우 → 오른쪽 절반 탐색
        else:
            start = mid + 1

    # 배열에서 요소를 찾지 못한 경우
    return -1

arr = sorted(['t', 'u', 't', 'o', 'r', 'i', 'a', 'l'])
x = 'r'
result = binary_search_iterative(arr, x)

if result != -1:
    print("Element is present at index " + str(result))
else:
    print("Element is not present in array")

실행 결과

Element is present at index 4

입력 리스트 ['t', 'u', 't', 'o', 'r', 'i', 'a', 'l']는 sorted() 함수에 의해 ['a', 'i', 'l', 'o', 'r', 't', 't', 'u']로 정렬되며, 찾고자 하는 문자 'r'은 인덱스 4 위치에 있음을 확인할 수 있습니다.

마무리

이번 글에서는 정렬된 리스트에서 원하는 값을 빠르게 찾는 이진 탐색 알고리즘의 핵심 원리를 이해하고, 재귀와 반복문 두 가지 방식으로 파이썬 코드를 직접 구현해 보았습니다. 두 방식 모두 시간 복잡도는 O(log n)으로 동일하지만, 코드의 가독성과 상황에 따라 적합한 방식을 선택해 사용하면 됩니다.