TIL - 이분 탐색

정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다.
• 변수 3개(start, end, mid)를 사용하여 탐색한다.
• 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해 원하는 데이터를 찾는다.
• 시간 복잡도는 O(log n)이다.
  • 탐색 범위를 절반씩 줄여 시간 복잡도를 보장한다.

Python으로 구현

재귀 함수

def binary_search(array, target, start, end):
  if start > end:
  	return -1
  mid = (start + end) // 2
  
  # 원하는 값을 찾은 경우 인덱스 반환
  if array[mid] == target:
    return mid
  # 원하는 값이 중간점의 값보다 작은 경우 (중간값 보다 큰 값의 인덱스 무시)
  elif array[mid] > target:
    return binary_search(array, target, start, mid - 1)
  # 원하는 값이 중간점의 값보다 큰 경우 (중간값 보다 작은 값의 인덱스 무시)
  else:
    return binary_search(array, target, mid + 1, end)

반복문

def binary_search(array, target, start, mid):
  while start <= end:
    mid = (start + end) // 2
    
    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
      
   return -1

Python 이진 탐색 라이브러리

bisect라는 이진 탐색 라이브러리(모듈)을 예제를 통해 알아보자.

bisect_left(array, x)

정렬된 순서를 유지하면서 리스트 array에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메소드

bisect_right(array, x)

정렬된 순서를 유지하도록 리스트 array에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메소드

from bisect import bisect_left, bisect_right
array = [1, 2, 4, 4, 8]
x = 4

print(biect_left(array, x))
>>> 2
# 리스트 array에 2를 삽입할 가장 왼쪽 인덱스는 2다.

print(bisect_right(array, x))
>>> 4
# 리스트 array에 4를 삽입할 가장 오른쪽 인덱스는 4다.

참고

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