[Python] bisect (이진 탐색)

[Python] bisect (이진 탐색)

bisect 라이브러리는 '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다.

• bisect의 두 가지 메서드

  1. bisect_left(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
  2. bisect_right(a, x): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

• 예시

  • 예를 들어 정렬된 리스트 a = [1, 2, 4, 4, 8]이 있을 때, 새롭게 데이터 4를 삽입하려 한다고 가정하자. 이때 bisect_left(a, 4)와 bisect_right(a, 4)는 각각 인덱스 값으로 2와 4를 반환한다.

• 소스코드 예시

  from bisect import bisect_left, bisect_right
  
  a = [1, 2, 4, 4, 8]
  x = 4
  
  print(bisect_left(a, x))
  print(bisect_right(a, x))
  
  # 출력 결과
  2
  4

또한 bisect_left()와 bisect_right() 메서드는 '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구할 때 유용하다. 아래의 경우를 살펴보자

• 예시

  # 아래의 count_by_range(a, left_value, right_value) 함수를 확인해보자. 이는 정렬된 리스트에서 값이 [left_value, right_value]에 속하는 데이터의 개수를 반환한다. 다시 말해 원소의 값을 x라고 할 때, left_value <= x <= right_value인 원소의 개수를 O(logN)으로 빠르게 계산 가능하다.
  
  from bisect import bisect_left, bisect_right
  
  def count_by_range(a, left_value, right_value):
      right_index = bisect_right(a, right_value)
      left_index = bisect_left(a, left_value)
      return right_index - left_index
  
  # 리스트 선언
  a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
  
  # 값이 4인 데이터 개수 출력
  print(count_by_range(a, 4, 4))
  
  # 값이 [-1, 3] 범위에 있는 데이터 개수 출력
  print(count_by_range(a, -1, 3))
  
  # 출력 결과
  2
  6