이진 검색 알고리즘

이진 검색은 정렬된 요소 목록이 입력으로 제공되는 알고리즘입니다. 목록에 찾고 있는 항목이 포함되어 있으면 알고리즘은 해당 위치에 대한 정보를 반환합니다. 그렇지 않으면 null 값을 반환합니다.

이진 검색에서 각 시도에서 나머지 숫자의 절반을 제거하기 위해 중간 숫자를 추측합니다.

def binnary_search(list, item):
    low = 0
    high = len(list) - 1  #1

    while low <= high:
        mid = round(low + high) // 2    #2
        guess = list[mid]

        if guess == item:     #3
            return mid
        if guess > item:      #4
            high = mid - 1
        else:                 #5
            low = mid + 1
    return None

my_list = [1, 2, 3, 5, 7, 9, 11, 23, 123, 345]

print(binnary_search(my_list, 345)) #9
print(binnary_search(my_list, 11)) #6
print(binnary_search(my_list, 15)) #None

이 프로그램을 다음과 같이 나누어 보겠습니다.

낮음 및 높음을 사용하여 목록에서 검색할 부분을 제어합니다.

검색 영역이 하나의 요소로 좁혀지지 않는 한 중간 요소를 선택합니다

요소가 발견됨

추측이 너무 큽니다

추측이 너무 낮습니다

그런 요소가 없습니다

목록의 번호 매기기는 0부터 시작한다는 것을 기억하십시오.

이진 검색은 전체 항목 목록을 하나씩 검색하는 좋은 대안입니다. 10개 요소 목록이 있는 이진 검색의 속도는 최대 4개의 추측을 제공하는 O(log 10)입니다.

Big O 표기법에 대한 자세한 내용은 이전 게시물에서 읽을 수 있습니다.