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

이분 탐색(Binary Search)은 정렬된 배열에서 특정 값을 빠르게 찾기 위한 효율적인 알고리즘입니다. 이 알고리즘은 배열을 반복적으로 반으로 나누면서 원하는 값을 찾는 방식으로 동작하며, 시간 복잡도가 O(logn)입니다. 이는 선형 탐색(Linear Search)의 O(n)과 비교할 때 훨씬 더 효율적입니다.

 

이분 탐색 알고리즘의 동작 원리

• 시작과 끝 설정: 배열의 시작점(low)과 끝점(high)을 설정합니다.
• 중간점 계산: 시작점과 끝점의 중간 인덱스(mid)를 계산합니다.
• 중간값 비교: 배열의 중간 값(arr[mid])과 찾고자 하는 값(target)을 비교합니다.
  • 만약 arr[mid]가 target과 같으면, 해당 인덱스를 반환합니다.
  • 만약 arr[mid]가 target보다 크면, target은 중간점보다 왼쪽에 있으므로 탐색 범위를 low부터 mid-1로 줄입니다.
  • 만약 arr[mid]가 target보다 작으면, target은 중간점보다 오른쪽에 있으므로 탐색 범위를 mid+1부터 high로 줄입니다.
• 반복: 위 과정을 반복하여 탐색 범위를 좁혀갑니다. low가 high보다 커지면 탐색을 종료하고, target이 없음을 의미하는 값을 반환합니다.

 

예시 코드

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2  # 중간 인덱스 계산
        if arr[mid] == target:
            return mid  # target을 찾았을 때, 인덱스를 반환
        elif arr[mid] < target:
            low = mid + 1  # target이 중간값보다 크면 오른쪽 탐색
        else:
            high = mid - 1  # target이 중간값보다 작으면 왼쪽 탐색
    
    return -1  # target이 없는 경우 -1 반환

# 예시: 정렬된 배열에서 이분 탐색
arr = [1, 3, 5, 7, 9, 11, 13, 15]
target = 7
result = binary_search(arr, target)

if result != -1:
    print(f"Element found at index {result}")
else:
    print("Element not found in array")

# 결과 값 출력
# Element found at index 3

 

설명

• low와 high: 배열의 시작과 끝 인덱스를 가리킵니다.
• mid: 현재 탐색 범위의 중간 인덱스입니다.
• 비교: 중간 값 arr[mid]를 target과 비교하여 탐색 범위를 좁혀갑니다.
• 시간 복잡도: 이분 탐색의 시간 복잡도는 O(log⁡n)으로, 매우 큰 배열에서도 빠르게 탐색할 수 있습니다.