Python中的二进制search（二分）

是否有库函数在列表/元组上执行二进制search，如果find则返回项目的位置，如果不是，则返回“False”（-1，None等）？

我在bisect模块中find了函数bisect_left / right，但是即使项目不在列表中，它们仍然会返回一个位置。 这对他们的预期用法是完全正确的，但我只想知道一个项目是否在列表中（不要插入任何东西）。

我想使用bisect_left ，然后检查该位置上的项目是否与我正在search的项目相同，但看起来很麻烦（而且我还需要进行界限检查，如果该数字可能大于我列表中的最大数字） 。 如果有更好的方法，我想知道它。

编辑为了澄清我需要这个：我知道一个字典将非常适合这个，但我试图保持尽可能低的内存消耗。 我的预期用法是一种双向查找表。 我在表中列出了一个值列表，我需要能够根据它们的索引访问值。 而且我也希望能够find一个特定值的索引，或者如果该值不在列表中，则为无。

使用字典这将是最快的方式，但会（大约）两倍的内存要求。

我在问这个问题，认为我可能忽略了Python库中的某些东西。 Moebuild议，似乎我必须写我自己的代码。

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

Answer 3

这是一个小题目（因为Moe的回答在OP的问题上似乎是完整的），但是可能值得从整个过程看整个过程的复杂性。 如果你将东西存储在一个有序的列表中（这是二进制search的帮助），然后只是检查是否存在，就会引起（最坏的情况，除非指定）：

sorting列表

• O（n log n）最初创build列表（如果它是未sorting的数据，O（n），如果sorting）
• O（log n）查找（这是二进制search部分）
• O（n）插入/删除（可能是O（1）或O（log n）平均大小写，取决于您的模式）

而set() ，你正在招致

• O（n）创build
• O（1）查找
• O（1）插入/删除

sorting列表真正得到的是“下一个”，“前一个”和“范围”（包括插入或删除范围），它们是O（1）或O（| range |），给定一个起始索引。 如果你不经常使用这些types的操作，那么作为集合存储和sorting显示可能是一个更好的交易。 set()在Python中引起很less的额外开销。

Answer 4

可能值得一提的是，对分文档现在提供了search示例： http : //docs.python.org/library/bisect.html#searching-sorted-lists

（例如，提高ValueError而不是返回-1或None更像pythonic – list.index（），但是当然你可以根据你的需要来调整例子。）

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。 searchsorting列表

上面的bisect（）函数对于查找插入点是很有用的，但是对于常见的search任务可能会非常棘手或笨拙。 以下五个函数显示如何将它们转换为已sorting列表的标准查找：

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

二等分模块不要求提前预先计算search数组。 您可以使用默认值0和len(a)将端点呈现给bisect.bisect_left而不是它。

对于我的使用来说，更重要的是寻找一个值X，使给定函数的误差最小化。 要做到这一点，我需要一种方法来让bisect_left的algorithm调用我的计算。 这很简单。

只要提供一个定义__getitem__为a对象

例如，我们可以使用对分algorithm来find任意精度的平方根！

 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

如果你只是想看看它是否存在，请尝试将列表转换为字典：

 # 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 in l”需要37秒，而“如果n in d”需要0.4秒。

Answer 9

戴夫·亚伯拉罕的解决scheme是好的。 虽然我已经做到了极简：

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

Answer 10

虽然在Python中没有明确的二进制searchalgorithm，但有一个模块 – bisect – devise为使用二分search为sorting列表中的元素find插入点。 这可以被“欺骗”到执行二进制search。 这样做的最大优点是大多数库代码具有相同的优势 – 它是高性能的，经过良好testing的，并且正常工作（二进制search特别是可能相当难以成功实现 – 特别是在边缘情况未被仔细考虑的情况下）。

基本types

对于像Strings或ints这样的基本types来说，这非常容易 – 所有你需要的是对bisect模块和一个sorting列表：

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

显然你可以返回索引，而不是索引值，如果需要的话。

对象

对于自定义的types或对象，事情有点棘手：你必须确保实现丰富的比较方法，以便正确比较对分。

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

这应该至less在Python 2.7 – > 3.3中工作

Answer 11

这一个是：

• 不recursion（这使得它比大多数recursion方法更具有内存效率 ）
• 实际上工作
• 快速，因为它运行没有任何不必要的条件和条件
• 基于math断言 （低+高）/ 2的底面总是小于高 ，其中低是下限而高是上限。
• testing：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 12

使用字典不会像你的内存使用加倍，除非你存储的对象是非常小的，因为这些值只是指向实际对象的指针：

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

在这个例子中，'foo'只存储一次。 这对你有好处吗？ 而究竟我们究竟在谈论多less项呢？

Answer 13

此代码以recursion方式处理整数列表。 寻找最简单的情况，即：列表长度小于2.这意味着答案已经存在，并执行testing以检查正确的答案。 如果不是，则设置中间值并且testing是正确的，如果不是通过再次调用该function来进行二等分，则将中间值设置为上限或下限，通过将其左右移动

 def binary_search（intList，intValue，lowValue，highValue）：
    如果（highValue  -  lowValue）<2：
        返回intList [lowValue] == intValue或intList [highValue] == intValue
     middleValue = lowValue +（（highValue  -  lowValue）/ 2）
    如果intList [middleValue] == intValue：
        返回True
    如果intList [middleValue]> intValue：
        返回binary_search（intList，intValue，lowValue，middleValue  -  1）
   返回binary_search（intList，intValue，middleValue + 1，highValue）

Answer 14

查看维基百科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 

我想这是更好，更有效。 请纠正我:)。 谢谢

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

二进制search：

 // 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中的二进制search和Django模型的通用。 在Django模型中，一个模型可以有另一个模型的外键，我想对检索到的模型对象进行一些search。 我写了下面的函数可以使用这个。

 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