Python中的二分搜索(平分)

是否有一个库函数，对列表/元组执行二进制搜索，并返回项目的位置，如果找到，如果没有'False' (-1, None等)?

我在二等分模块中找到了bisect_left/right函数，但即使项目不在列表中，它们仍然返回一个位置。这对于它们的预期用途来说是非常好的，但我只是想知道一个项目是否在列表中(不想插入任何东西)。

我想使用bisect_left，然后检查该位置的项是否等于我正在搜索的内容，但这似乎很麻烦(而且我还需要做边界检查，如果这个数字可以大于列表中最大的数字)。如果有更好的方法，我想知道。

编辑来澄清我需要这个:我知道字典将非常适合这个，但我试图保持内存消耗尽可能低。我的预期用途是一种双向查找表。我在表中有一个值列表，我需要能够访问基于其索引的值。我还希望能够找到特定值的索引，如果值不在列表中，则为None。

使用字典是最快的方法，但(大约)会增加一倍的内存需求。

我问这个问题时认为我可能忽略了Python库中的一些东西。看来我得自己写代码了，就像Moe建议的那样。

210320 次浏览
小开

为什么不看看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
小开

如果你只是想看看它是否存在，试着把这个列表变成一个词典:

# 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秒。

小开

这有点跑题了(因为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(|范围|)，给定一个起始索引。如果你不经常使用这些类型的操作，那么存储为集合，排序显示可能是一个更好的整体交易。set()在python中引起的额外开销非常小。

小开

使用dict不会使内存使用量翻倍，除非你存储的对象非常小，因为这些值只是指向实际对象的指针:

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

在这个例子中，'foo'只存储了一次。这对你有影响吗?我们到底要谈多少项呢?

小开

最简单的方法是使用平分并返回检查一个位置，看看项目是否在那里:

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
小开
最佳答案

bisect_left找到元素在给定排序范围内插入的第一个位置p，同时保持排序顺序。这将是x的位置，如果x存在于范围内。如果p是末尾位置，则没有找到x。否则，我们可以测试是否存在x，看看是否找到了x。

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
小开
值得一提的是，bisect文档现在提供了搜索示例: http://docs.python.org/library/bisect.html#searching-sorted-lists < / p >

(引发ValueError而不是返回-1或None更加python化——例如，list.index()会这样做。当然，你也可以根据自己的需要调整这些例子。)

小开
这段代码以递归的方式处理整数列表。寻找最简单的情况，即:列表长度小于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)
小开 
'''
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

我想这样更好更有效。请纠正我:)。谢谢你！

小开

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

戴夫·亚伯拉罕斯的解决方案很好。虽然我会把它做得极简:

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

我同意@DaveAbrahams的回答使用bisect模块是正确的方法。他在回答中没有提到一个重要的细节。

从文档 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)
小开

虽然Python中没有显式的二进制搜索算法，但有一个模块——bisect——设计用于使用二进制搜索在排序列表中查找元素的插入点。这可以被“欺骗”为执行二分搜索。这最大的优势是大多数库代码都具有的优势-它是高性能的，经过良好测试的，并且可以工作(特别是二进制搜索可以很难成功实施 -特别是如果没有仔细考虑边缘情况)。

基本类型

对于基本类型，如string或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中工作

小开

这是手册上的内容:

http://docs.python.org/2/library/bisect.html < a href = " 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
小开
  • 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)
小开

这个是基于数学断言， (低+高)/2的地板总是小于高，其中低是下限，高是上限。

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
小开

我需要二进制搜索python和通用的Django模型。在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
小开 
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))
小开

上面有很多好的解决方案，但我还没有看到一个简单的(KISS保持简单(因为我是)愚蠢的使用Python内置/通用平分函数来做二进制搜索。使用bisect函数的一些代码，我想下面有一个示例，其中我测试了一个小字符串数组的所有情况。上面的一些解决方案提到了这一点，但希望下面的简单代码能帮助像我一样困惑的人。

Python二分法用于指示在排序列表中插入新值/搜索项的位置。下面的代码使用bisect_left，如果在列表/数组中找到搜索项，它将返回命中的索引(注意bisect和bisect_right将返回命中或匹配后的元素索引作为插入点)如果没有找到，bisect_left将返回排序列表中下一项的索引，该索引将不==搜索值。唯一的另一种情况是，搜索项将位于列表的末尾，返回的索引将超出列表/数组的末尾，并且在下面的代码中用“and”逻辑句柄提前退出。(第一个条件False 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
小开

你好，这是我的python实现没有平分。如果可以改进，请告诉我。

def bisectLeft(a, t):
lo = 0
hi = len(a) - 1
ans = None
# print("------lower------")
# print(a, t)
while lo <= hi:
mid = (lo + hi) // 2
# print(a[lo:mid], [a[mid]], a[mid:hi])
if a[mid] < t:
lo = mid + 1
elif a[mid] > t:
hi = mid - 1
elif a[mid] == t:
if mid == 0: return 0
if a[mid-1] != t: return mid
hi = mid - 1
            

return ans


def bisectRight(a, t):
lo = 0
hi = len(a) - 1
ans = None
# print("------upper------")
# print(a, t)
while lo <= hi:
mid = (lo + hi) // 2
# print(a[lo:mid], [a[mid]], a[mid:hi])
if a[mid] == t:
ans = mid
if a[mid] <= t:
lo = mid + 1
else:
hi = mid - 1
return ans
小开

我想使用bisect_left，然后检查是否在那项 position等于我要搜索的内容，但这看起来很麻烦 (我还需要做边界检查，如果数字可以更大 而不是我列表中最大的数字)。如果有更好的方法，我会

避免边界检查或相等性检查的一种方法是同时运行bisect_left ()和bisect_right ():

def find(data, target):
start = bisect_left(data, target)
end = bisect_right(data, target)
return -1 if start == end else start

提交答案