검색(양방향)에서 Python

Question

이 있는 라이브러리 함수 수행하는 바이너리에서 검색 목록이/tuple 및익 항목의 위치를 발견하는 경우고'False'(-1,None,etc.) 하지 않을 경우?

내가 찾는 기능 bisect_left/오른쪽에서 계획 모듈, 지만,그들은 여전히 반환에 위치하는 경우에도지 않은 품목에서는 목록에 있습니다.는 완벽한 사용 목적지만,나는 단지 알고 싶다면 항목에서는 목록 또는지(지를 삽입하려는 아무것도).

의 생각을 사용하여 bisect_left 인 경우 항목에서는 위치를 동일 내가 무엇을 찾으로 이러한 성가(그리고 내가 또한 필요한 경계 검사를 경우에는 수보다 큰에서 가장 많은 수 my list).이 있는 경우는 더 좋은 방법에 대해 알고 싶습니다.

편집 을 명확히 무엇이 필요:내가 알고 있는 사전에 매우 적합하이,하지만 노력하고 메모리를 유지하기 위해 소비를 최대한 낮추는 것입니다.내 의도된 사용을 것 두 방법 모니다.나는 테이블에서 값의 목록 및 필요에 액세스할 수 있는 값에 따라 자신의 인덱스입니다.또한하고 싶을 찾을 수 있 인덱스의 특정 값이나도 없지 않은 경우에는 목록에 있습니다.

를 사용에 대한 사전이 될 것이 가장 빠른 방법이지만,(대략적인 금액)두 번의 메모리 요구 사항이 있습니다.

나는 이 질문을 생각하는 경우가 있을 수 있습니다 것을 간과에서 뭔가를 Python 라이브러리입니다.그것은 보인다 나는 내 자신을 쓰기 코드,모에 제안했다.

Answer 1

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

Answer 2

보이지 않는 이유에 대한 코드를 bisect_left/오른쪽에 적응에 맞게 그것을 당신의 목적이 있다.

다음과 같다:

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

Answer 3

이것은 조금 떨어져 화제(이후 모 답변을 보인 완료하는 영업 이익의 질문)지만,그것을 찾고 가치가있을 수도 있습니다에서의 복잡성에 대한 전체적인 절차를 끝에서 끝에 있습니다.만약 당신이 저장하는 일에 정렬된 목록(여기에서 검색을 도울 것),다음을 확인하기 위해 존재,부딪히고 있(최악의 경우,지정하지 않은 경우):

정렬된 목록

• O(n 로그 n)처음에 목록을 만드(있을 경우 그것은 정렬하지 않고 데이터입니다.O(n)는 경우,그것은 분류)
• O(로그 n)조회(이 검색부분)
• O(n)insert/delete(수 있습 O(1),O(로그 n)평균 경우에 따라 패턴)

반면 set(), 에,당신은 발생

• O(n)을 만들기
• O(1)조회
• O(1)insert/delete

것을 정렬된 목록을 정말 당신을 얻은"다음"을"이",및""범위(포함하여 삽입 또는 삭제 범위),는 O(1),O(|범위|),주어진 시작 인덱스입니다.사용하지 않는 경우에는 그 종류의 작업은 종종 다음으로 저장하트 및 분류에 대한 표시될 수 있는 더 나은 거래 전반적인. set() 초래에 아주 작은 추가적인 오버헤드에서 python.

Answer 4

그것은 될 수 있는 것을 언급 할 가치 계획서 문서를 제공 찾 예제:http://docs.python.org/library/bisect.html#searching-sorted-lists

(육 ValueError 반환하는 대신 -1 또는 아무도 더 pythonic–목록입니다.인덱스()는 그것은,예를 들어.하지만 물론에 적응할 수 있습니다 귀하의 필요합니다.)

Answer 5

가장 간단을 사용하는 것입 계획 확인 중 하나는 위치에 다시 볼 경우에는 품목이 있:

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

Answer 6

이것은 오른쪽에서 수동:

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

8.5.1.검색로 정렬된 목록

위의 계획()함수를 찾는 데 유용 삽입 포지 까다로운 일이 될 수 있는 어색한 사용에 대한 일반적인 검색 작업이 있습니다.다음과 같은 다섯 가지 기능을 표시하는 방법으로 변환합한 표준에 대한 검색 목록을 정렬:

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

Answer 7

는 것에 동의 @DaveAbrahams 의 응답 를 사용하여 계획 모듈을 올바른 접근 방식이다.그는 언급하지 않았다 하나의 중요한 세부에 그의 대답이다.

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

이분의 모듈을 필요로하지 않습 검색 배열을 미리 계산된다.할 수 있습니다 그냥 현재의 끝점을 bisect.bisect_left 대신 그것을 사용하는 기본값의 0 고 len(a).

더 많은 중요한 내용을 찾고,값 X 는 오류의 주어진 기능이 최소화됩니다.저는 방법이 필요하 bisect_left 의 알고리즘을 내 계산 대신 합니다.이것은 정말 간단합니다.

제공하는 개체의 정의 __getitem__ 로 a

예를 들어,우리가 사용할 수 있는 계획 알고리즘을 찾아 사용하여 근 임의의 정밀도!

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)

Answer 8

는 경우 당신은 여부를 확인하려면 현재,하려고 도는 목록으로 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

내 컴퓨터에서,"n 경우에는"37 초안 경우"n d"했 0.4 초입니다.

Answer 9

이 중 하나입니다:

• 지 않을 재귀(세요 메모리 효율 보다 가장 재귀적인 접근 방식)
• 실제로 일
• 빠른 이후 실행하지 않고 불필요한 면의 과 조건
• 에 따라 수학적 주장을 그 의 바닥(low+high)/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

Answer 10

Dave 아브라함'솔루션은 좋습니다.수도 있지만 그것을 한 것이 최소한의:

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

Answer 11

은 없습니다하지만 명시적으 검색 알고리즘에서는 Python,이 모듈 bisect -찾을 수 있도록 설계되었 삽입 지점을 위해 요소를 정렬된 목록을 사용하여 검색.이 될 수 있습니다"속으로"을 수행하는 바이너리 search.의 가장 큰 장점이 동일한 장점은 대부분의 라이브러리 코드가있다-그것은 고성능,뿐만 아니라 그냥 일(binary 검색에 특정할 수 있다 매우 어렵 성공적으로 구현하는 -는 경우에 특히 가리지 않는 경우 신중하게 간주됩니다).

기본적인 유형

에 대한 기본적인 유형과 같은 문자열이나 수것은 매우 쉽게 당신이 필요로하는 모든 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']

이 작업에는 적어도 Python2.7->3.3

Answer 12

를 사용하여 dict 지 않을 것 같은 두 번의 메모리를 사용하지 않는 한 개체를 저장하는 정말 작은,때문에 이 값은 단지 포인터가 실제 물체:

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

이 예제에서'foo'은 한 번만 저장되.가 차이를 만드는가?정확히 얼마나 많은 항목에 대해서 이야기해 우리는 어쨌든?

Answer 13

이 코드와 함께 작동이 정수로 목록을 재귀적 방법입니다.를 찾는 가장 간단한 경우,어떤은 다음과 같습니다:목록 길이보다 2.그것은 대답은 이미 거기 및 테스트를 수행하는 검사에 대한 올바른 대답이다.하지 않을 경우,중간 값을 설정하고 테스트를 수확하지 않을 경우,이분이 수행를 호출하여 다시 기능만 설정 값으로 상거나 낮은 제한을 이동시킴으로써 그것을 왼쪽 또는 오른쪽으로

def binary_search(intList, intValue, lowValue, highValue):
    if(highValue - lowValue) < 2:
        return intList[lowValue] == intValue or intList[highValue] == intValue
    middleValue = lowValue + ((highValue - lowValue)/2)
    if intList[middleValue] == intValue:
        return True
    if intList[middleValue] > intValue:
        return binary_search(intList, intValue, lowValue, middleValue - 1)
   return binary_search(intList, intValue, middleValue + 1, highValue)

Answer 14

체크아웃 예 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

Answer 15

'''
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

난 이것은 훨씬 더 효과적입니다.정하시기 바랍 me:).감사

Answer 16

• 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)
  

Answer 17

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

Answer 18

바이너리로 검색:

// 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))

Answer 19

나는 데 필요한 바이너리에서 검색 python 및 일반적인을 위한 장고의 모델입니다.에 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

Answer 20

많은 좋은 해결책 위에 그러나 나는 보지 못 간단(KISS 간단(나)어리석의 사용 Python 내에 일반적인 계획 할 수있는 기능을 이진 검색합니다.의 비트와 함께 코드위 계획 기능,내가 생각하는 예 아래는 내가 테스트에 대한 모든 경우 작은 문 배의 이름입니다.위 솔루션을 언급/말하지만,무슨 말인지 이해하길 바란 간단한 코드를 아는 사람들을 도움이 될 것입니다 혼란 다음과 같았습니다.

파이썬은 계획을 사용하는 위치를 나타내 삽입하는 새로운 값을 검색 항목으로 정렬된 목록입니다.아래 코드를 사용하는 bisect_left 으로 돌아갈 수 있는 인덱스의 경우 검색 항목 목록에서/배열을 발견된(주의 계획 및 bisect_right 반환 요소의 인덱스트의 히트 후 또는 경기로 삽입 지점에)발견되지 않는 경우는,bisect_left 돌아 인덱스는 다음 항목에서 정렬된 목록하지 않습니다==색 값입니다.만 다른 경우는 어디서 검색 항목을 갈 것이의 끝 부분에 목록는 반환되는 것을 넘어 목록의 끝/배열하는 코드에서는 아래의 조기 종료에 의해 파이썬"및"논리를 처리합니다.(첫째 조건이 거짓 Python 지 않을 확인한 후속 조건)

#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