8.1 이진 탐색 알고리즘
이진 탐색 알고리즘(binary search algorithm)은 정렬된 데이터로 된 리스트(배열이나 연결 리스트)가 인수로 들어왔을 때 요소 중에 찾고자 하는 데이터가 있는지 알아보는 알고리즘입니다. 여기서 중요한 점은 인수로 전달된 리스트 요소들이 정렬되어 있다는 것입니다. 코드를 보고 작동 과정을 조금 생각해 봅시다.
코드 8-1 binary_search.py
def binary_search(li, target):
"""
인자로 전달된 리스트 요소는 정렬되어 있습니다.
"""
start = 0
end = len(li) - 1
while start <= end:
middle = (start+end) // 2
if li[middle] == target:
return middle
elif li[middle] > target:
end = middle - 1
else:
start = middle + 1
return None