[python] 파이썬에서 이진 검색 (이분법)

목록 / 튜플에서 이진 검색을 수행하고 발견되면 항목의 위치를 반환하고 그렇지 않으면 ‘False'(-1, None 등)를 반환하는 라이브러리 함수가 있습니까?

bisect 모듈 에서 bisect_left / right 함수를 찾았습니다 지만 항목이 목록에 없어도 여전히 위치를 반환합니다. 의도 된 사용법에는 완벽하게 적합하지만 항목이 목록에 있는지 여부를 알고 싶습니다 (삽입하고 싶지 않음).

bisect_left해당 위치의 항목이 검색중인 항목과 같은지 확인하고 사용하는 것을 생각 했지만 번거로운 것처럼 보입니다 (그리고 내 목록에서 가장 큰 수보다 큰 수인지 확인하는 경계 검사도 필요합니다). 더 좋은 방법이 있다면 그것에 대해 알고 싶습니다.

편집하다 내가 필요한 것을 명확히하려면 : 사전이 이것에 매우 적합하다는 것을 알고 있지만 가능한 한 메모리 소비를 줄이려고합니다. 내 의도 된 사용법은 일종의 양방향 조회 테이블입니다. 테이블에 값 목록이 있으며 해당 색인을 기반으로 값에 액세스 할 수 있어야합니다. 또한 특정 값의 인덱스를 찾거나 값이 목록에 없으면 None을 찾고 싶습니다.

이를 위해 사전을 사용하는 것이 가장 빠른 방법이지만 메모리 요구량을 (대략적으로) 두 배로 늘릴 것입니다.

파이썬 라이브러리에서 뭔가 간과했을 수도 있다고 생각 하면서이 질문을하고있었습니다. Moe가 제안한 것처럼 내 코드를 작성해야 할 것 같습니다.

답변

from bisect import bisect_left

def binary_search(a, x, lo=0, hi=None):  # can't use a to specify default for hi
    hi = hi if hi is not None else len(a)  # hi defaults to 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 / right의 코드를보고 목적에 맞게 조정 해보십시오.

이처럼 :

def binary_search(a, x, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        midval = a[mid]
        if midval < x:
            lo = mid+1
        elif midval > x:
            hi = mid
        else:
            return mid
    return -1

답변

이것은 Moe의 답변이 OP의 질문에 완전 해 보이기 때문에 약간의 주제가 아니지만 전체 절차의 복잡성을 끝까지 검토하는 것이 좋습니다. 정렬 된 목록 (이진 검색이 도움이되는 곳)에 물건을 저장하고 존재 여부를 확인하는 경우 (지정하지 않는 한 최악의 경우) 발생합니다.

정렬 된 목록

O (n log n)로 처음에 목록을 작성합니다 (정렬되지 않은 데이터 인 경우 정렬 된 경우 O (n)).
O (log n) 조회 (이진 검색 부분)
O (n) 삽입 / 삭제 (패턴에 따라 O (1) 또는 O (log n) 평균 경우 일 수 있음)

을 (를) 사용하는 set()동안에는

만들 O (n)
O (1) 조회
O (1) 삽입 / 삭제

정렬 된 목록에서 실제로 얻을 수있는 것은 시작 색인이 주어지면 “다음”, “이전”및 “범위”(범위 삽입 또는 삭제 포함)입니다 (O (1) 또는 O (| range |)). 이러한 종류의 작업을 자주 사용하지 않는 경우 세트로 저장하고 디스플레이를 정렬하면 전체적으로 더 나은 결과를 얻을 수 있습니다. set()파이썬에서 추가 오버 헤드가 거의 발생하지 않습니다.

답변

bisect 문서는 이제 검색 예제를 제공한다고 언급 할 가치가 있습니다.
http://docs.python.org/library/bisect.html#searching-sorted-lists

예를 들어 -1을 반환하는 대신 ValueError를 올리거나 None을 사용하는 것이 더 pythonic입니다. list.index ()가이를 수행합니다.

답변

가장 간단한 방법은 bisect 를 사용 하고 한 위치를 다시 확인하여 항목이 있는지 확인하는 것입니다.

def binary_search(a,x,lo=0,hi=-1):
    i = bisect(a,x,lo,hi)
    if i == 0:
        return -1
    elif a[i-1] == x:
        return i-1
    else:
        return -1

답변

이것은 매뉴얼에서 옳습니다.

http://docs.python.org/2/library/bisect.html

8.5.1. 정렬 된 목록 검색

위의 bisect () 함수는 삽입 점을 찾는 데 유용하지만 일반적인 검색 작업에 사용하기 까다 롭거나 어색 할 수 있습니다. 다음 5 가지 함수는 정렬 된 목록에 대한 표준 조회로 변환하는 방법을 보여줍니다.

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

따라서 약간 수정하면 코드는 다음과 같아야합니다.

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

답변

@DaveAbrahams의 답변에 동의합니다.bisect 모듈을 사용하는 이 올바른 접근 방법 . 그는 그의 대답에 중요한 세부 사항을 언급하지 않았습니다.

로부터 문서 bisect.bisect_left(a, x, lo=0, hi=len(a))

이 분할 모듈은 검색 배열을 미리 미리 계산할 필요가 없습니다. 당신은 단지에 엔드 포인트를 제시 할 수 bisect.bisect_left의 기본값을 사용하여 대신 0하고len(a) .

주어진 기능의 오류가 최소화되도록 X 값을 찾아서 사용하는 것이 더 중요합니다. 이를 위해서는 bisect_left의 알고리즘이 내 계산을 대신 호출하는 방법이 필요했습니다. 이것은 정말 간단합니다.

정의하는 객체를 제공하십시오. __getitem__ 과 같이a

예를 들어, bisect 알고리즘을 사용하여 임의의 정밀도로 제곱근을 찾을 수 있습니다!

import bisect

class sqrt_array(object):
    def __init__(self, digits):
        self.precision = float(10**(digits))
    def __getitem__(self, key):
        return (key/self.precision)**2.0

sa = sqrt_array(4)

# "search" in the range of 0 to 10 with a "precision" of 0.0001
index = bisect.bisect_left(sa, 7, 0, 10*10**4)
print 7**0.5
print index/(10**4.0)