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

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

---

목록 / 튜플에서 이진 검색을 수행하고 발견되면 항목의 위치를 ​​반환하고 그렇지 않으면 '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

---

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

로부터 문서 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)

---

존재하는지 확인하려면 목록을 dict로 바꾸십시오.

# Generate a list
l = [n*n for n in range(1000)]

# Convert to dict - doesn't matter what you map values to
d = dict((x, 1) for x in l)

count = 0
for n in range(1000000):
    # Compare with "if n in l"
    if n in d:
        count += 1

내 컴퓨터에서 "if n in l"은 37 초, "if n in d"는 0.4 초가 걸렸습니다.

---

이것은 :

• 재귀 적 아님 ( 대부분의 재귀 적 접근법보다 메모리 효율성이 높음)
• 실제로 작동
• 불필요한 if 와 조건 없이 실행 되기 때문에 빠릅니다.
• 수학적 주장에 기초 한다는 의 층 (저 + 높은)은 / 2 보다 항상 작 높은 곳 낮음 하한이고 높이가 상한이다.
• 테스트 : D

---

def binsearch(t, key, low = 0, high = len(t) - 1):
    # bisecting the range
    while low < high:
        mid = (low + high)//2
        if t[mid] < key:
            low = mid + 1
        else:
            high = mid
    # at this point 'low' should point at the place
    # where the value of 'key' is possibly stored.
    return low if t[low] == key else -1

---

Dave Abrahams의 솔루션이 좋습니다. 비록 최소한으로 했었을지라도 :

def binary_search(L, x):
    i = bisect.bisect_left(L, x)
    if i == len(L) or L[i] != x:
        return -1
    return i

---

파이썬에는 명시적인 이진 검색 알고리즘이 없지만 이진 검색을 bisect사용하여 정렬 된 목록에서 요소의 삽입 지점을 찾도록 설계된 모듈이 있습니다. 이진 검색을 수행하는 데 "속임수"가있을 수 있습니다. 이것의 가장 큰 장점은 대부분의 라이브러리 코드가 가진 장점과 동일합니다. 성능이 뛰어나고 잘 테스트되었으며 작동합니다 (특히 이진 검색은 성공적으로 구현하기 가 매우 어려울 수 있습니다 -특히 엣지 케이스를 신중하게 고려하지 않는 경우).

기본 유형

Strings 또는 int와 같은 기본 유형의 경우 매우 쉽습니다. bisect모듈과 정렬 된 목록 만 있으면 됩니다.

>>> import bisect
>>> names = ['bender', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> bisect.bisect_left(names, 'fry')
1
>>> keyword = 'fry'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
True
>>> keyword = 'arnie'
>>> x = bisect.bisect_left(names, keyword)
>>> names[x] == keyword
False

이것을 사용하여 중복을 찾을 수도 있습니다.

...
>>> names = ['bender', 'fry', 'fry', 'fry', 'leela', 'nibbler', 'zoidberg']
>>> keyword = 'fry'
>>> leftIndex = bisect.bisect_left(names, keyword)
>>> rightIndex = bisect.bisect_right(names, keyword)
>>> names[leftIndex:rightIndex]
['fry', 'fry', 'fry']

분명히 원하는 경우 해당 색인의 값 대신 색인을 반환 할 수 있습니다.

사물

사용자 정의 유형 또는 객체의 경우 상황이 약간 까다로워집니다. 이등분을 올바르게 비교하려면 풍부한 비교 방법을 구현해야합니다.

>>> import bisect
>>> class Tag(object):  # a simple wrapper around strings
...     def __init__(self, tag):
...         self.tag = tag
...     def __lt__(self, other):
...         return self.tag < other.tag
...     def __gt__(self, other):
...         return self.tag > other.tag
...
>>> tags = [Tag('bender'), Tag('fry'), Tag('leela'), Tag('nibbler'), Tag('zoidbe
rg')]
>>> key = Tag('fry')
>>> leftIndex = bisect.bisect_left(tags, key)
>>> rightIndex = bisect.bisect_right(tags, key)
>>> print([tag.tag for tag in tags[leftIndex:rightIndex]])
['fry']

이것은 적어도 Python 2.7-> 3.3에서 작동해야합니다.

---

값이 실제 객체에 대한 포인터 일 뿐이므로 저장하는 객체가 실제로 작지 않으면 dict를 사용하는 것이 메모리 사용량을 두 배로 늘리는 것을 좋아하지 않습니다.

>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True

이 예에서 'foo'는 한 번만 저장됩니다. 그것이 당신에게 차이가 있습니까? 어쨌든 우리는 몇 개의 항목에 대해 이야기하고 있습니까?

---

이 코드는 정수 목록과 재귀적인 방식으로 작동합니다. 가장 간단한 시나리오를 찾습니다.리스트 길이가 2보다 작습니다. 이는 이미 답변이 있고 정답을 확인하기위한 테스트를 수행함을 의미합니다. 그렇지 않은 경우, 중간 값이 설정되고 올바른지 테스트합니다. 이분법을 다시 호출하여이 분할을 수행하지 않고 중간 값을 왼쪽 또는 오른쪽으로 이동하여 중간 값을 상한 또는 하한으로 설정

데프 바이너리 _ 검색 (intList, intValue, lowValue, highValue) :
    if (highValue-lowValue) <2 :
        intList [lowValue] == intValue 또는 intList [highValue] == intValue를 반환합니다.
    middleValue = lowValue + ((고가-저가) / 2)
    intList [middleValue] == intValue 인 경우 :
        True를 반환
    intList [middleValue]> intValue 인 경우 :
        binary_search (intList, intValue, lowValue, middleValue-1) 반환
   binary_search (intList, intValue, middleValue + 1, highValue) 반환

---

Wikipedia http://en.wikipedia.org/wiki/Binary_search_algorithm 에서 예제를 확인하십시오 .

def binary_search(a, key, imin=0, imax=None):
    if imax is None:
        # if max amount not set, get the total
        imax = len(a) - 1

    while imin <= imax:
        # calculate the midpoint
        mid = (imin + imax)//2
        midval = a[mid]

        # determine which subarray to search
        if midval < key:
            # change min index to search upper subarray
            imin = mid + 1
        elif midval > key:
            # change max index to search lower subarray
            imax = mid - 1
        else:
            # return index number 
            return mid
    raise ValueError

---

'''
Only used if set your position as global
'''
position #set global 

def bst(array,taget): # just pass the array and target
        global position
        low = 0
        high = len(array)
    while low <= high:
        mid = (lo+hi)//2
        if a[mid] == target:
            position = mid
            return -1
        elif a[mid] < target: 
            high = mid+1
        else:
            low = mid-1
    return -1

나는 이것이 훨씬 더 좋고 효과적이라고 생각한다. 나를 수정하십시오 :). 감사합니다

---

• s 목록입니다.
• binary(s, 0, len(s) - 1, find) 초기 통화입니다.

• 함수는 쿼리 된 항목의 인덱스를 반환합니다. 그러한 항목이 없으면를 반환합니다 -1.

  def binary(s,p,q,find):
      if find==s[(p+q)/2]:
          return (p+q)/2
      elif p==q-1 or p==q:
          if find==s[q]:
              return q
          else:
              return -1
      elif find < s[(p+q)/2]:
          return binary(s,p,(p+q)/2,find)
      elif find > s[(p+q)/2]:
          return binary(s,(p+q)/2+1,q,find)
  

---

def binary_search_length_of_a_list(single_method_list):
    index = 0
    first = 0
    last = 1

    while True:
        mid = ((first + last) // 2)
        if not single_method_list.get(index):
            break
        index = mid + 1
        first = index
        last = index + 1
    return mid

---

이진 검색 :

// List - values inside list
// searchItem - Item to search
// size - Size of list
// upperBound - higher index of list
// lowerBound - lower index of list
def binarySearch(list, searchItem, size, upperBound, lowerBound):
        print(list)
        print(upperBound)
        print(lowerBound)
        mid = ((upperBound + lowerBound)) // 2
        print(mid)
        if int(list[int(mid)]) == value:
               return "value exist"
        elif int(list[int(mid)]) < value:
             return searchItem(list, value, size, upperBound, mid + 1)
        elif int(list[int(mid)]) > value:
               return searchItem(list, value, size, mid - 1, lowerBound)

// 위의 함수를 호출하려면 다음을 사용하십시오.

list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
searchItem = 1        
print(searchItem(list[0], item, len(list[0]) -1, len(list[0]) - 1, 0))

---

파이썬에서 바이너리 검색이 필요했고 장고 모델에는 일반 검색이 필요했습니다. Django 모델에서 한 모델은 다른 모델에 대한 외래 키를 가질 수 있으며 검색 된 모델 객체에 대한 검색을 원했습니다. 나는 당신이 이것을 사용할 수있는 다음 기능을 썼습니다.

def binary_search(values, key, lo=0, hi=None, length=None, cmp=None):
    """
    This is a binary search function which search for given key in values.
    This is very generic since values and key can be of different type.
    If they are of different type then caller must specify `cmp` function to
    perform a comparison between key and values' item.
    :param values:  List of items in which key has to be search
    :param key: search key
    :param lo: start index to begin search
    :param hi: end index where search will be performed
    :param length: length of values
    :param cmp: a comparator function which can be used to compare key and values
    :return: -1 if key is not found else index
    """
    assert type(values[0]) == type(key) or cmp, "can't be compared"
    assert not (hi and length), "`hi`, `length` both can't be specified at the same time"

    lo = lo
    if not lo:
        lo = 0
    if hi:
        hi = hi
    elif length:
        hi = length - 1
    else:
        hi = len(values) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if not cmp:
            if values[mid] == key:
                return mid
            if values[mid] < key:
                lo = mid + 1
            else:
                hi = mid - 1
        else:
            val = cmp(values[mid], key)
            # 0 -> a == b
            # > 0 -> a > b
            # < 0 -> a < b
            if val == 0:
                return mid
            if val < 0:
                lo = mid + 1
            else:
                hi = mid - 1
    return -1

---

Many good solutions above but I haven't seen a simple (KISS keep it simple (cause I'm) stupid use of the Python built in/generic bisect function to do a binary search. With a bit of code around the bisect function, I think I have an example below where I have tested all cases for a small string array of names. Some of the above solutions allude to/say this, but hopefully the simple code below will help anyone confused like I was.

Python bisect is used to indicate where to insert an a new value/search item into a sorted list. The below code which uses bisect_left which will return the index of the hit if the search item in the list/array is found (Note bisect and bisect_right will return the index of the element after the hit or match as the insertion point) If not found, bisect_left will return an index to the next item in the sorted list which will not == the search value. The only other case is where the search item would go at the end of the list where the index returned would be beyond the end of the list/array, and which in the code below the early exit by Python with "and" logic handles. (first condition False Python does not check subsequent conditions)

#Code
from bisect import bisect_left
names=["Adam","Donny","Jalan","Zach","Zayed"]
search=""
lenNames = len(names)
while search !="none":
    search =input("Enter name to search for or 'none' to terminate program:")
    if search == "none":
        break
    i = bisect_left(names,search)
    print(i) # show index returned by Python bisect_left
    if i < (lenNames) and names[i] == search:
        print(names[i],"found") #return True - if function
    else:
        print(search,"not found") #return False – if function
##Exhaustive test cases:
##Enter name to search for or 'none' to terminate program:Zayed
##4
##Zayed found
##Enter name to search for or 'none' to terminate program:Zach
##3
##Zach found
##Enter name to search for or 'none' to terminate program:Jalan
##2
##Jalan found
##Enter name to search for or 'none' to terminate program:Donny
##1
##Donny found
##Enter name to search for or 'none' to terminate program:Adam
##0
##Adam found
##Enter name to search for or 'none' to terminate program:Abie
##0
##Abie not found
##Enter name to search for or 'none' to terminate program:Carla
##1
##Carla not found
##Enter name to search for or 'none' to terminate program:Ed
##2
##Ed not found
##Enter name to search for or 'none' to terminate program:Roger
##3
##Roger not found
##Enter name to search for or 'none' to terminate program:Zap
##4
##Zap not found
##Enter name to search for or 'none' to terminate program:Zyss
##5
##Zyss not found

참고URL : https://stackoverflow.com/questions/212358/binary-search-bisection-in-python