Python中的二进制搜索(二等分)

问题:Python中的二进制搜索(二等分)

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

我在bisect模块中找到了bisect_left / right函数,但是即使该项目不在列表中,它们仍然会返回位置。这对于他们的预期用途来说是完全可以的,但是我只想知道列表中是否有项目(不想插入任何内容)。

我考虑过使用bisect_left然后检查该位置处的项目是否等于我要搜索的项目,但这似乎很麻烦(而且我还需要进行边界检查,以检查数字是否可以大于列表中最大的数字)。如果有更好的方法,我想知道。

编辑为了弄清楚我需要什么:我知道字典将非常适合此操作,但是我试图将内存消耗保持在尽可能低的水平。我的预期用途是一种双向查询表。表中有一个值列表,我需要能够根据它们的索引访问值。而且我还希望能够找到特定值的索引,或者如果该值不在列表中,则查找None。

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

我问这个问题的原因是我可能忽略了Python库中的某些内容。就像Moe建议的那样,看来我必须编写自己的代码。

Is there a library function that performs binary search on a list/tuple and return the position of the item if found and ‘False’ (-1, None, etc.) if not?

I found the functions bisect_left/right in the bisect module, but they still return a position even if the item is not in the list. That’s perfectly fine for their intended usage, but I just want to know if an item is in the list or not (don’t want to insert anything).

I thought of using bisect_left and then checking if the item at that position is equal to what I’m searching, but that seems cumbersome (and I also need to do bounds checking if the number can be larger than the largest number in my list). If there is a nicer method I’d like to know about it.

Edit To clarify what I need this for: I’m aware that a dictionary would be very well suited for this, but I’m trying to keep the memory consumption as low as possible. My intended usage would be a sort of double-way look-up table. I have in the table a list of values and I need to be able to access the values based on their index. And also I want to be able to find the index of a particular value or None if the value is not in the list.

Using a dictionary for this would be the fastest way, but would (approximately) double the memory requirements.

I was asking this question thinking that I may have overlooked something in the Python libraries. It seems I’ll have to write my own code, as Moe suggested.


回答 0

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_left finds the first position p at which an element could be inserted in a given sorted range while maintaining the sorted order. That will be the position of x if x exists in the range. If p is the past-the-end position, x wasn’t found. Otherwise, we can test to see if x is there to see if x was found.

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

回答 1

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

Why not look at the code for bisect_left/right and adapt it to suit your purpose.

like this:

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

回答 2

这有点题外话了(因为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()在python中几乎不会产生额外的开销。

This is a little off-topic (since Moe’s answer seems complete to the OP’s question), but it might be worth looking at the complexity for your whole procedure from end to end. If you’re storing thing in a sorted lists (which is where a binary search would help), and then just checking for existence, you’re incurring (worst-case, unless specified):

Sorted Lists

  • O( n log n) to initially create the list (if it’s unsorted data. O(n), if it’s sorted )
  • O( log n) lookups (this is the binary search part)
  • O( n ) insert / delete (might be O(1) or O(log n) average case, depending on your pattern)

Whereas with a set(), you’re incurring

  • O(n) to create
  • O(1) lookup
  • O(1) insert / delete

The thing a sorted list really gets you are “next”, “previous”, and “ranges” (including inserting or deleting ranges), which are O(1) or O(|range|), given a starting index. If you aren’t using those sorts of operations often, then storing as sets, and sorting for display might be a better deal overall. set() incurs very little additional overhead in python.


回答 3

可能值得一提的是,bisect文档现在提供了搜索示例:http : //docs.python.org/library/bisect.html#searching-sorted-lists

(例如,使用ValueError而不是返回-1或None而不是返回python更为有用–例如list.index()可以。但是当然,您可以根据需要调整示例。)

It might be worth mentioning that the bisect docs now provide searching examples: http://docs.python.org/library/bisect.html#searching-sorted-lists

(Raising ValueError instead of returning -1 or None is more pythonic – list.index() does it, for example. But of course you can adapt the examples to your needs.)


回答 4

最简单的方法是使用等分并向后检查一个位置以查看该项目是否存在:

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

Simplest is to use bisect and check one position back to see if the item is there:

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

回答 5

这是正确的手册:

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

8.5.1。搜索排序列表

上面的bisect()函数对于查找插入点很有用,但是对于常见的搜索任务而言可能会有些棘手或笨拙。以下五个函数显示了如何将它们转换为排序列表的标准查找:

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

This is right from the manual:

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

8.5.1. Searching Sorted Lists

The above bisect() functions are useful for finding insertion points but can be tricky or awkward to use for common searching tasks. The following five functions show how to transform them into the standard lookups for sorted lists:

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

So with the slight modification your code should be:

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

回答 6

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

来自文档 bisect.bisect_left(a, x, lo=0, hi=len(a))

二等分模块不需要提前对搜索数组进行预先计算。您可以bisect.bisect_left使用和的默认值,仅将端点显示给0len(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)

I agree that @DaveAbrahams’s answer using the bisect module is the correct approach. He did not mention one important detail in his answer.

From the docs bisect.bisect_left(a, x, lo=0, hi=len(a))

The bisection module does not require the search array to be precomputed ahead of time. You can just present the endpoints to the bisect.bisect_left instead of it using the defaults of 0 and len(a).

Even more important for my use, looking for a value X such that the error of a given function is minimized. To do that, I needed a way to have the bisect_left’s algorithm call my computation instead. This is really simple.

Just provide an object that defines __getitem__ as a

For example, we could use the bisect algorithm to find a square root with arbitrary precision!

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)

回答 7

这是:

  • 不是递归的(这使其比大多数递归方法更有效地利用内存
  • 实际工作
  • 快速运行,因为它运行时没有任何不必要条件
  • 基于数学断言(低+高)/ 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

This one is:

  • not recursive (which makes it more memory-efficient than most recursive approaches)
  • actually working
  • fast since it runs without any unnecessary if’s and conditions
  • based on a mathematical assertion that the floor of (low + high)/2 is always smaller than high where low is the lower limit and high is the upper limit.

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

回答 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

在我的机器上,“ if n in l”花费了37秒,而“ if n in d”花费了0.4秒。

If you just want to see if it’s present, try turning the list into a 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

On my machine, “if n in l” took 37 seconds, while “if n in d” took 0.4 seconds.


回答 9

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

Dave Abrahams’ solution is good. Although I have would have done it minimalistic:

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

回答 10

尽管Python中没有显式的二进制搜索算法,但有一个模块-bisect用于使用二进制搜索在排序列表中查找元素的插入点。这可以“诱骗”执行二进制搜索。这种方法的最大优点是大多数库代码都具有相同的优点-高性能,经过良好测试并且可以正常工作(特别是二进制搜索很难成功实现-尤其是在没有仔细考虑边缘情况的情况下)。

基本类型

对于像字符串或整数这样的基本类型,这非常简单-您所需要的只是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中有效

While there’s no explicit binary search algorithm in Python, there is a module – bisect – designed to find the insertion point for an element in a sorted list using a binary search. This can be “tricked” into performing a binary search. The biggest advantage of this is the same advantage most library code has – it’s high-performing, well-tested and just works (binary searches in particular can be quite difficult to implement successfully – particularly if edge cases aren’t carefully considered).

Basic Types

For basic types like Strings or ints it’s pretty easy – all you need is the bisect module and a sorted list:

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

You can also use this to find duplicates:

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

Obviously you could just return the index rather than the value at that index if desired.

Objects

For custom types or objects, things are a little bit trickier: you have to make sure to implement rich comparison methods to get bisect to compare correctly.

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

This should work in at least Python 2.7 -> 3.3


回答 11

除非您要存储的对象非常小,否则使用dict不会使您的内存使用量增加一倍,因为这些值只是指向实际对象的指针:

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

在该示例中,“ foo”仅存储一次。这对您有影响吗?我们到底要谈论多少个项目?

Using a dict wouldn’t like double your memory usage unless the objects you’re storing are really tiny, since the values are only pointers to the actual objects:

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

In that example, ‘foo’ is only stored once. Does that make a difference for you? And exactly how many items are we talking about anyway?


回答 12

此代码以递归方式处理整数列表。查找最简单的情况,即:列表长度小于2。这意味着答案已经存在,并且将进行测试以检查正确答案。如果不是,则设置中间值并将其测试为正确的值;如果未进行二等分,则通过再次调用该函数,但通过将其向左或向右移动,将中间值设置为上限或下限

def binary_search(intList,intValue,lowValue,highValue):
    if(highValue-lowValue)<2:
        返回intList [lowValue] == intValue或intList [highValue] == intValue
    middleValue =低值+((高值-低值)/ 2)
    如果intList [middleValue] == intValue:
        返回True
    如果intList [middleValue]> intValue:
        返回binary_search(intList,intValue,lowValue,middleValue-1)
   返回binary_search(intList,intValue,middleValue + 1,highValue)

This code works with integer lists in a recursive way. Looks for the simplest case scenario, which is: list length less than 2. It means the answer is already there and a test is performed to check for the correct answer. If not, a middle value is set and tested to be the correct, if not bisection is performed by calling again the function, but setting middle value as the upper or lower limit, by shifting it to the left or right

def binary_search(intList, intValue, lowValue, highValue):
    if(highValue - lowValue) &lt 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)

回答 13

在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

Check out the examples on 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

回答 14

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

我想这会更好,更有效。请纠正我:)。谢谢

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

I guess this is much better and effective. please correct me :) . Thank you


回答 15

  • 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)
    
  • s is a list.
  • binary(s, 0, len(s) - 1, find) is the initial call.
  • Function returns an index of the queried item. If there is no such item it returns -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)
    

回答 16

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

回答 17

二进制搜索:

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

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

// To call above function use :

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

回答 18

我需要在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

I needed binary search in python and generic for Django models. In Django models, one model can have foreign key to another model and I wanted to perform some search on the retrieved models objects. I wrote following function you can use this.

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

回答 19

上面有很多好的解决方案,但是我还没有看到一个简单的(KISS保持简单(因为我是愚蠢的)愚蠢地使用内置的Python /通用bisect函数来进行二进制搜索。在bisect函数周围有一些代码,我想在下面的示例中,我已经测试了所有情况下的小型字符串数组,上面的一些解决方案也暗示/说明了这一点,但是希望下面的简单代码可以像我一样帮助任何困惑的人。

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

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