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

이분 / 이진 탐색 (Binary Search) ?

정렬된 리스트에서 특정 값을 찾는 데 사용되는 효율적인 알고리즘이다.
리스트의 중앙값과 목표 값을 비교하여 목표 값이 중앙값보다 작으면 리스트의 왼쪽 절반을 탐색하고 크면 리스트의 오른쪽 절반을 탐색하는 방식으로 진행된다. 이렇게 계속해서 리스트를 반씩 줄여 나가면서 값을 찾는다.

 

 

이분 / 이진 탐색 알고리즘의 단계

1. 초기화: 리스트의 처음과 끝 인덱스 설정
2. 반복 또는 재귀: 중앙값을 계산하고 이 값을 목표 값과 비교
3. 값 비교:
   • 목표 값 = 중앙값 → 해당 인덱스 반환
   • 목표 값 < 중앙값 → 리스트의 왼쪽 절반 탐색
   • 목표 값이 > 중앙값 → 리스트의 오른쪽 절반 탐색
4. 반복 종료: 리스트의 탐색 범위가 0이 되면 목표 값이 리스트에 없는 것으로 간주하고 탐색 종료

 

이분 / 이진 탐색 알고리즘의 시간 복잡도

O(log n)으로 리스트의 크기를 반으로 줄여 나가는 특성 덕분에 매우 효율적이다.

 

 

이분 / 이진 탐색하는 방법

이분 탐색을 사용할 때는 반드시 리스트가 정렬되어 있어야 한다!

• 반복문 사용

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

  return -1  # 값을 찾지 못했을 경우 -1 반환

• 재귀 사용

def bs(arr, target, left, right):
  if left > right:
    return -1  # 값을 찾지 못했을 경우 -1 반환

  mid = (left + right) // 2
  
  if arr[mid] == target:
    return mid
  elif arr[mid] < target:
    return bs(arr, target, mid + 1, right)
  else:
    return bs(arr, target, left, mid - 1)

 

 

이분 / 이진 탐색 라이브러리 (파이썬)

• bisect_left(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환
• bisect_right(a, x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽 인덱스를 반환

from bisect import bisect_left, bisect_right

arr = [1, 2, 4, 4, 4, 5, 6, 8, 9]

left_index = bisect_left(arr, 4)   # 2
right_index = bisect_right(arr, 4) # 5