Python을 사용하여 이진 검색을 구현하는 방법-파이썬 튜토리얼-php.cn

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

WBOY

풀어 주다： 2023-05-11 10:40:05

앞으로

3253명이 탐색했습니다.

먼저, 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] < value: 찾을 값은 mid의 오른쪽에 있고, 왼쪽의 값을 mid로 업데이트하고 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을 사용하여 이진 검색을 구현하는 방법