摘要：问题描述：是否有一个库函数可以对列表/元组执行二进制搜索，如果找到则返回项目的位置，如果没有找到则返回“False”（-1，None 等）？我在bisect 模块中找到了 bisect_left/right 函数，但即使项目不在列表中，它们仍会返回一个位置。这对于它们的预期用途来说完全没问题，但我只想知道某个...

问题描述：

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

我在bisect 模块中找到了 bisect_left/right 函数，但即使项目不在列表中，它们仍会返回一个位置。这对于它们的预期用途来说完全没问题，但我只想知道某个项目是否在列表中（不想插入任何内容）。

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

编辑为了澄清我需要这个的原因：我知道字典非常适合这个，但我试图将内存消耗保持在尽可能低的水平。我打算使用一种双向查找表。我在表中有一个值列表，我需要能够根据它们的索引访问这些值。而且我还希望能够找到特定值的索引，如果该值不在列表中，则找到 None。

对于这种情况，使用字典是最快的方法，但会使内存需求（大约）增加一倍。

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

解决方案 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

解决方案 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

解决方案 3：

这有点离题（因为 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 中几乎不会产生额外的开销。

解决方案 4：

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

（引发 ValueError 而不是返回 -1 或 None 更符合 Python 风格，例如 list.index() 就是这样做的。当然，您可以根据需要调整示例。）

解决方案 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

解决方案 6：

这是手册上的说法：

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

解决方案 7：

这个是基于一个数学断言，即(low + high)/2 的下限总是小于上限，其中low是下限，high是上限。

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：

我同意@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)

解决方案 9：

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

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

解决方案 10：

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

解决方案 11：

查看维基百科上的示例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

解决方案 12：

虽然 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 中工作

解决方案 13：

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

避免边界检查或检查项目是否相等的一种方法是同时运行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

解决方案 14：

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

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

在这个例子中，“foo”只存储了一次。这对你来说有什么不同吗？而且我们到底在谈论多少个项目？

解决方案 15：

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

def binary_search（intList，intValue，lowValue，highValue）：
    如果（高值 - 低值）<2：
        返回 intList[lowValue] == intValue 或 intList[highValue] == intValue
    中间值 = 低值 + ((高值 - 低值)/2)
    如果 intList[middleValue] == intValue:
        返回 True
    如果 intList[middleValue] > intValue:
        返回二分搜索（intList，intValue，lowValue，middleValue - 1）
   返回二分搜索（intList，intValue，middleValue + 1，highValue）

解决方案 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)

解决方案 17：

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

我想这个更好、更有效。请纠正我 :)。谢谢

解决方案 18：

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

解决方案 19：

二分查找：

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

解决方案 20：

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

解决方案 21：

上面有很多好的解决方案，但我还没有看到一个简单的（KISS保持简单（因为我）愚蠢地使用Python内置/通用二分函数进行二分搜索。使用二分函数的一些代码，我想我有下面一个例子，我已经测试了名称的小字符串数组的所有情况。上面的一些解决方案暗示/说过这一点，但希望下面的简单代码可以帮助任何像我一样困惑的人。

Python bisect 用于指示在排序列表中插入新值/搜索项的位置。下面的代码使用 bisect_left，如果在列表/数组中找到搜索项，它将返回命中的索引（注意 bisect 和 bisect_right 将返回命中或匹配后的元素的索引作为插入点）如果没有找到，bisect_left 将返回排序列表中下一个项的索引，该索引不会 == 搜索值。唯一的另一种情况是搜索项将位于列表末尾，返回的索引将超出列表/数组的末尾，在下面的代码中，Python 使用“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

解决方案 22：

你好，这是我的没有二分法的 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

Python 中的二分搜索（二分法）