Python에서 이진 검색을 사용하여 정렬된 목록에 항목이 있는지 효율적으로 확인하려면 어떻게 해야 합니까?

명시적 항목 존재 검사를 사용하는 Python의 이진 검색(이등분)

Python bisect 모듈은 bisect_left와 같은 이진 검색을 수행하는 함수를 제공합니다. 그리고 bisect_right. 그러나 이러한 함수는 검색 중인 항목이 목록에 없는 경우에도 위치를 반환합니다. 항목의 유무만 원하는 경우에는 보다 명시적인 확인이 필요합니다.

한 가지 접근 방식은 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

이 함수는 정렬된 목록 a, 대상 값 x, 선택적인 검색 하한 및 상한을 사용합니다. bisect_left를 사용하여 x에 대한 삽입 지점을 찾은 다음 해당 위치의 항목이 대상과 일치하는지 확인합니다. 일치하는 항목이 발견되면 함수는 위치를 반환합니다. 그렇지 않으면 -1을 반환하여 항목이 없음을 나타냅니다.

이 명시적 검사를 통합하면 불필요한 오버헤드나 제한을 도입하지 않고도 정렬된 목록에 항목이 있는지 여부를 효율적으로 확인할 수 있습니다.

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