Python을 사용하여 이진 검색을 구현하는 방법

먼저, bin_search라는 함수를 만듭니다. 두 개의 매개변수, 즉 요소 목록과 찾으려는 값을 전달합니다.

def binary_search(_list, value):

다음으로 함수 내부에 필요한 변수를 정의합니다. 이분법의 핵심은 목록의 중앙에서 양쪽으로 검색하는 것입니다(표현이 엄밀하지는 않지만 아마도 이것이 의미하는 바일 것입니다). 직관, 왼쪽, 오른쪽, 중간을 정의하십시오. 세 가지 변수는 목록의 시작 인덱스, 끝 인덱스 및 중간 인덱스를 나타냅니다.

    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置

다음 단계는 이진 검색의 핵심 부분을 구현하는 것입니다. 먼저 검색이 원활하게 진행될 수 있도록 while 루프를 정의합니다. 조건부 판단을 구현하기 위해 분기 문이 중첩되는 경우:

1. _list[mid] == value: 중간 값이 우리가 찾아야 할 값이 되므로 해당 인덱스를 직접 반환하면 됩니다.

2._list[mid] > value: 찾을 값은 mid의 왼쪽에 있습니다. 검색 범위를 좁히려면 오른쪽의 값을 mid로 업데이트하세요.

3._list[mid]

마지막으로 다음 검색을 시작하기 위해 mid 값을 업데이트하고 while-else 문을 사용하여 찾을 수 없는지 판단하고 반환 값을 제공합니다.

    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1

마지막으로 완성된 코드와 테스트 실행 성능은 다음과 같습니다.

""" a demo realize binary search"""
 
 
def binary_search(_list, value):
    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置
    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1
 
 
index = "the index of value in the list: {}"
print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))

실행 결과:

찾을 값이 없는 경우:

위 내용은 Python을 사용하여 이진 검색을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!