이진 탐색 (Binary Search)
목차
탐색할 자료를 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법. 둘(binary)로 해석하기보다 양자택일로 해석하는 것이 이해하기 쉽다.
특징
- 정렬된 상태에서만 사용 가능
- 리스트의 중간을 선택하여 탐색 값을 비교, 크고 작음에 따라 좌우 선택
- 재귀를 사용하여 1개가 남을 때까지 반복
구현
def binary_search(data, find):
if len(data) == 1:
return find == data[0]
mid = len(data) // 2
if find == data[mid]:
return True
if find > data[mid]:
selected_list = data[mid + 1:]
else:
selected_list = data[:mid]
return binary_search(selected_list, find)시간 복잡도
n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산 k회: O(log n)