더북(TheBook)

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

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.