Python bisect 모듈 이용한 이진 탐색

• 파이썬 알고리즘 인터뷰 65번(리트코드 704) Binary Search의 풀이를 보니 이진 탐색 모듈 bisect가 있었다.
• 이진 탐색을 직접 구현하는 것은 많이 해보았는데 이 모듈을 사용해보진 않았다.
• bisect 모듈을 이용하는 방법을 정리해보자.

아래 내용은 GPT를 이용하여 정리하였다.

"""
bisect 모듈은 정렬된 리스트에서 이진 탐색을 활용하여 효율적으로 값을 삽입하거나 찾는 기능을 제공하는 모듈입니다.
이 모듈을 사용하면 O(log N) 시간 복잡도로 탐색이 가능하며, O(N)으로 정렬된 리스트에 원소를 삽입할 수 있습니다.
특히, 정렬된 리스트에서 특정 값의 개수를 찾거나, 빠르게 삽입할 때 유용합니다.

주요 함수:
- bisect_left(a, x): 정렬된 리스트에서 x가 들어갈 왼쪽 경계 인덱스 반환
- bisect_right(a, x): 정렬된 리스트에서 x가 들어갈 오른쪽 경계 인덱스 반환
- bisect(a, x): bisect_right()의 별칭 (동일한 기능)
- insort_left(a, x): x를 정렬된 리스트의 왼쪽 경계에 삽입
- insort_right(a, x): x를 정렬된 리스트의 오른쪽 경계에 삽입
- insort(a, x): insort_right()의 별칭 (동일한 기능)

특이사항:
- tuple 자료형에서는 bisect 검색은 가능하지만, insort로 값을 삽입할 수 없음.
- list와 array.array는 검색과 삽입 모두 가능.
- set과 dict는 bisect를 사용할 수 없음.
"""

import bisect

# 1. bisect 모듈 주요 함수
a = [1, 3, 4, 4, 7]

# 1-1. bisect_left(a, x): x가 들어갈 왼쪽 경계 인덱스 반환
print(bisect.bisect_left(a, 4))  # 결과: 2

# 1-2. bisect_right(a, x): x가 들어갈 오른쪽 경계 인덱스 반환
print(bisect.bisect_right(a, 4))  # 결과: 4

# 1-3. bisect(a, x): bisect_right()의 별칭 (동일한 동작)
print(bisect.bisect(a, 4))  # 결과: 4

# 2. 정렬된 리스트에 원소 삽입
nums = [10, 20, 30, 40]

# 2-1. insort_left(a, x): 왼쪽 경계에 삽입
bisect.insort_left(nums, 25)
print(nums)  # 결과: [10, 20, 25, 30, 40]

# 2-2. insort_right(a, x): 오른쪽 경계에 삽입
bisect.insort_right(nums, 25)
print(nums)  # 결과: [10, 20, 25, 25, 30, 40]

# 2-3. insort(a, x): insort_right()의 별칭 (동일한 동작)
bisect.insort(nums, 35)
print(nums)  # 결과: [10, 20, 25, 25, 30, 35, 40]

# 3. 특정 값의 개수 찾기 (bisect_right - bisect_left)
def count_occurrences(arr, x):
    return bisect.bisect_right(arr, x) - bisect.bisect_left(arr, x)

a = [1, 2, 2, 2, 3, 4, 5]
print(count_occurrences(a, 2))  # 결과: 3

# 4. tuple에서 bisect 검색 가능 (삽입 불가능)
t = (1, 3, 5, 7)
print(bisect.bisect_left(t, 4))  # 결과: 2 (검색 가능)
print(bisect.bisect_right(t, 4))  # 결과: 2 (검색 가능)

try:
    bisect.insort_left(t, 4)  # TypeError 발생 (튜플은 변경 불가능)
except TypeError as e:
    print(f"튜플에 삽입 불가능: {e}")

# 5. array.array에서도 bisect 사용 가능
import array

arr = array.array('i', [1, 3, 5, 7])
bisect.insort(arr, 4)
print(arr)  # 결과: array('i', [1, 3, 4, 5, 7])

자료형	🔍 검색(bisect_left, bisect_right)	✏️ 삽입(insort_left, insort_right)	이유
list	✅ 가능	✅ 가능	변경 가능하고 순서 보장
tuple	✅ 가능	❌ 불가능	불변(immutable) 자료형이라 변경 불가
array.array	✅ 가능	✅ 가능	리스트와 유사한 배열 자료형
set	❌ 불가능	❌ 불가능	순서 보장 X, 인덱스로 접근 불가
dict	❌ 불가능	❌ 불가능	키-값 구조이며 순서 탐색 불가