PYTHON · 컬렉션
bisect 이진 검색
bisect로 정렬된 리스트에서 이진 검색과 삽입을 O(log n)에 수행합니다.
컬렉션중급bisect이진 검색binary search정렬
핵심 설명
bisect로 정렬된 리스트에서 이진 검색과 삽입을 O(log n)에 수행합니다.
Python code
import bisect
# 정렬된 리스트에 삽입 위치 찾기
data = [10, 20, 30, 40, 50]
pos = bisect.bisect(data, 25)
print(f"25의 삽입 위치: {pos}") # 2
# insort: 삽입 위치에 바로 추가
bisect.insort(data, 25)
print(data) # [10, 20, 25, 30, 40, 50]
# 성적 등급 매기기
def grade(score):
breakpoints = [60, 70, 80, 90]
grades = "FDCBA"
return grades[bisect.bisect(breakpoints, score)]
scores = [33, 60, 77, 85, 92, 100]
for s in scores:
print(f" {s}점 → {grade(s)}등급")
# bisect_left vs bisect_right
arr = [1, 3, 3, 3, 5, 7]
print(bisect.bisect_left(arr, 3)) # 1 (왼쪽)
print(bisect.bisect_right(arr, 3)) # 4 (오른쪽)
# 정렬된 리스트에서 값 검색
def binary_search(arr, target):
i = bisect.bisect_left(arr, target)
if i < len(arr) and arr[i] == target:
return i
return -1
print(binary_search(arr, 3)) # 1
print(binary_search(arr, 4)) # -1학습 팁
bisect_left와 bisect_right의 차이는 동일한 값이 있을 때 왼쪽/오른쪽에 삽입하는지입니다.
주의할 점
bisect는 정렬된 리스트에서만 올바르게 동작합니다. 정렬되지 않은 리스트에서 사용하면 잘못된 결과가 나옵니다.
자주 묻는 질문
bisect 이진 검색란 무엇인가요?
bisect 로 정렬된 리스트에서 이진 검색과 삽입을 O(log n)에 수행합니다.
bisect 이진 검색 학습 시 주의할 점은 무엇인가요?
bisect 는 정렬된 리스트에서만 올바르게 동작합니다. 정렬되지 않은 리스트에서 사용하면 잘못된 결과가 나옵니다.