항목 존재 여부를 확인하기 위해 Python에서 이진 검색을 효율적으로 구현하려면 어떻게 해야 합니까?

Python의 이진 검색(후광 검색)

Python은 이진 검색(이진 검색이라고도 함)을 구현하는 라이브러리 함수를 제공하며, 정렬된 목록이나 튜플의 항목입니다. 그러나 항목을 찾을 수 없는 경우에도 이러한 함수는 위치를 반환합니다.

이 문제를 해결하고 항목이 존재하는지 감지하는 한 가지 방법은 bisect.bisect_left() 함수를 사용하여 삽입 위치를 찾은 다음 해당 위치의 항목이 대상 항목과 동일한지 확인하는 것입니다. . 그러나 이는 지루할 수 있으며 숫자가 목록에서 가장 큰 숫자보다 큰 경우 경계 확인이 필요합니다.

메모리 소모로 인해 질문에 사전을 대안으로 제안했습니다. 그러나 이 경우 메모리 요구 사항이 약 두 배 정도 필요할 수 있습니다.

따라서 이 문제는 사용자 정의 코드를 사용하여 이진 검색을 구현하면 해결될 수 있습니다.

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)
    pos = bisect_left(a, x, lo, hi)                 # find insertion position
    return pos if pos != hi and a[pos] == x else -1  # don't walk off the end

이 함수는 bisect_left() 함수를 사용하여 삽입 위치를 찾는데, 이는 삽입 위치를 나타냅니다. 존재하는 경우 대상 항목을 표시하고, 존재하지 않는 경우 범위를 벗어난 위치를 나타냅니다. 해당 위치의 항목이 대상 항목과 동일한지 확인하여 대상 항목이 존재하는지 여부를 확인할 수 있습니다.

위 내용은 항목 존재 여부를 확인하기 위해 Python에서 이진 검색을 효율적으로 구현하려면 어떻게 해야 합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!