PYTHON · 컬렉션
이진 검색
이진 검색 알고리즘을 직접 구현하고 bisect과 비교합니다.
컬렉션고급binary search이진 검색알고리즘bisect
핵심 설명
이진 검색 알고리즘을 직접 구현하고 bisect과 비교합니다.
Python code
import bisect
from typing import Optional
def binary_search(arr: list, target) -> Optional[int]:
"""이진 검색: O(log n)"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return None
# 하한/상한 검색
def lower_bound(arr, target):
"""target 이상인 첫 번째 위치"""
return bisect.bisect_left(arr, target)
def upper_bound(arr, target):
"""target 초과인 첫 번째 위치"""
return bisect.bisect_right(arr, target)
data = [1, 3, 3, 3, 5, 7, 9]
print(f"검색 3: 인덱스={binary_search(data, 3)}")
print(f"하한 3: {lower_bound(data, 3)}") # 1
print(f"상한 3: {upper_bound(data, 3)}") # 4
print(f"3의 개수: {upper_bound(data, 3) - lower_bound(data, 3)}") # 3
# 조건 기반 이진 검색
def find_min_satisfying(lo, hi, predicate):
while lo < hi:
mid = (lo + hi) // 2
if predicate(mid):
hi = mid
else:
lo = mid + 1
return lo
# x^2 >= 100인 최소 x
result = find_min_satisfying(0, 100, lambda x: x * x >= 100)
print(f"x²≥100인 최소 x: {result}") # 10학습 팁
조건 기반 이진 검색(parametric search)은 최적화 문제를 O(log n)으로 풀 수 있는 강력한 기법입니다.
주의할 점
(left + right) // 2는 매우 큰 수에서 오버플로 가능합니다. Python은 임의 정밀도이므로 문제없지만, 다른 언어에서는 left + (right - left) // 2를 사용합니다.
자주 묻는 질문
이진 검색란 무엇인가요?
이진 검색 알고리즘을 직접 구현하고 bisect 과 비교합니다.
이진 검색 학습 시 주의할 점은 무엇인가요?
(left + right) // 2 는 매우 큰 수에서 오버플로 가능합니다. Python은 임의 정밀도이므로 문제없지만, 다른 언어에서는 left + (right - left) // 2 를 사용합니다.