Python 이진 검색 알고리즘
로그 O(log n) 시간으로 정렬된 목록을 검색합니다. 단계별 논리, 극단적 사례, 최적화를 포함하여 Python에서 이진 검색을 실행하고 이해하세요.
개요
이진 검색은 정렬된 목록에서 항목을 찾는 매우 효율적인 알고리즘입니다. O(n) 시간에 모든 요소를 순차적으로 검색하는 선형 검색과 달리 이진 검색은 검색 간격을 반복적으로 절반으로 나누어 작동합니다.
검색은 배열의 중간 요소를 검사하는 것으로 시작됩니다. 대상 값이 중간 요소와 일치하면 해당 위치가 반환됩니다. 대상이 더 작으면 알고리즘은 검색 범위를 아래쪽 절반으로 좁힙니다. 목표가 더 크면 상반부로 좁혀집니다. 이 프로세스는 요소를 찾거나 하위 배열 크기가 0으로 떨어질 때까지 반복됩니다.
Python에서 이진 검색을 구현하기 위해 두 개의 포인터(낮음 및 높음)를 사용하여 활성 검색 경계를 추적합니다. 각 단계에서 검색 공간이 절반으로 줄어들기 때문에 알고리즘은 O(log n) 시간에 실행되므로 대규모 데이터베이스에 이상적입니다.
코드 및 실행 출력
정렬된 목록에서 대상 요소의 인덱스를 반환하는 표준 반복 이진 검색 구현입니다.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return -1
# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23
index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
print(f"Target found at index: {index}")
else:
print("Target not found in dataset")Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5단계별 구현
- 데이터베이스 테이블의 쿼리 인덱싱 및 검색
- 연속적인 수학 범위에서 임계값 또는 경계값 찾기
- 텍스트 필드의 자동 완성 및 검색 기능
자주 묻는 질문
이진 검색이 작동하려면 목록을 정렬해야 합니까?
예, 이진 검색은 정렬되는 요소에 엄격하게 의존합니다. 목록이 정렬되지 않은 경우 비교 논리가 중단되므로 먼저 목록을 정렬하거나 선형 검색을 사용해야 합니다.
재귀 이진 검색 대신 반복 이진 검색을 사용하는 이유는 무엇입니까?
재귀 이진 검색은 우아하지만 프로덕션 환경에서는 반복 이진 검색이 선호되는 경우가 많습니다. 반복적 접근 방식은 O(1) 보조 공간에서 실행되는 반면 재귀 검색은 호출 스택으로 인해 O(log n) 공간을 차지하므로 매우 큰 입력에서 스택 오버플로가 발생할 위험이 있습니다.