161

是否有一个库函数在列表/元组上执行二进制搜索并返回项目的位置（如果找到）和'False'（-1，无等等），如果没有？

我在bisect module中找到了函数bisect_left / right，但即使该项不在列表中，它们仍会返回一个位置 . 那's perfectly fine for their intended usage, but I just want to know if an item is in the list or not (don' t想插入任何东西） .

我想到使用 bisect_left 然后检查那个位置的项目是否等于我想知道的那个 .

Edit 为了澄清我的需要：I 'm aware that a dictionary would be very well suited for this, but I' m试图尽可能降低内存消耗 . 我的预期用法是一种双向查找表 . 我在表中有一个值列表，我需要能够根据它们的索引访问这些值 . 而且如果值不在列表中，我希望能够找到特定值的索引或None .

使用字典是最快的方法，但会（大约）加倍内存需求 .

我在问这个问题，认为我可能忽略了Python库中的某些东西 . 正如Moe建议的那样，我似乎必须编写自己的代码 .

20 回答

s 是一个列表 .
binary(s, 0, len(s) - 1, find) 是初始通话 .
Function返回查询项的索引 . 如果没有这样的项目，则返回 -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)

回复于 2024-05-14T04:43:26+08:00

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

回复于 2024-05-14T04:43:26+08:00

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

回复于 2024-05-14T04:43:26+08:00

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

回复于 2024-05-14T04:43:26+08:00

54
这有点偏离主题（因为Moe的回答似乎完全符合OP的问题），但可能值得从头到尾查看整个过程的复杂性 . 如果您将事物存储在已排序的列表中（这是二进制搜索有帮助的地方），然后只检查是否存在，则会产生（最坏情况，除非指定）：

Sorted Lists
- O（n log n）最初创建列表（如果's unsorted data. O(n), if it'已排序）
- O（log n）查找（这是二进制搜索部分）
- O（n）插入/删除（可能是O（1）或O（log n）平均情况，具体取决于您的模式）
而set()，你正在招致
- O（n）来创建
- O（1）查找
- O（1）插入/删除
在给定起始索引的情况下，排序列表真正得到的是"next"，"previous"和"ranges"（包括插入或删除范围），它们是O（1）或O（| range |） . 如果您不经常使用这些类型的操作，那么存储为集合以及排序显示可能会更好 . set()在python中产生很少的额外开销 .
回复于 2024-05-14T04:43:26+08:00
1

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

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

回复于 2024-05-14T04:43:26+08:00

最简单的方法是使用bisect并检查一个位置以查看该项目是否存在：

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

回复于 2024-05-14T04:43:26+08:00

7
这是正确的手册：

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
```
回复于 2024-05-14T04:43:26+08:00
2
我同意@DaveAbrahams's answer使用bisect模块是正确的方法 . 他没有在答案中提到一个重要的细节 .

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

二分模块不需要提前预先计算搜索数组 . 您可以使用 0 和 len(a) 的默认值将 endpoints 呈现给 bisect.bisect_left 而不是它 .

对我来说更重要的是，寻找值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)
```
回复于 2024-05-14T04:43:26+08:00

如果您只想查看它是否存在，请尝试将列表转换为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 in l”需要37秒，而“if n in d”需要0.4秒 .

回复于 2024-05-14T04:43:26+08:00

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

回复于 2024-05-14T04:43:26+08:00

虽然Python中没有明确的二进制搜索算法，但有一个模块-- bisect - 旨在使用二进制搜索查找排序列表中元素的插入点 . 这可以"tricked"进行二进制搜索 . 这样做的最大优点是大多数库代码具有相同的优势 - 它性能高，经过良好测试并且正常工作（特别是二进制搜索可以是quite difficult to implement successfully - 特别是如果不仔细考虑边缘情况） .

基本类型

对于像Strings或ints这样的基本类型，它非常简单 - 您只需要 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']

显然，如果需要，您可以返回索引而不是索引处的值 .

对象

对于自定义类型或对象，事情有点棘手：您必须确保实现丰富的比较方法以使bisect能够正确比较 .

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

回复于 2024-05-14T04:43:26+08:00

217

这个是：

不是递归的（这比大多数递归方法更多 memory-efficient ）
实际 working
快了 runs without any unnecessary if's and conditions
based on a mathematical assertion （低值）/ 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

回复于 2024-05-14T04:43:26+08:00

0
除非您存储的对象非常小，否则使用dict不会使内存使用量增加一倍，因为值只是指向实际对象的指针：
```
>>> a = 'foo'
>>> b = [a]
>>> c = [a]
>>> b[0] is c[0]
True
```
在该示例中，'foo'仅存储一次 . 这对你有影响吗？究竟有多少项目我们还在讨论？
回复于 2024-05-14T04:43:26+08:00

此代码以递归方式与整数列表一起使用 . 寻找最简单的情况，即：列表长度小于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)

回复于 2024-05-14T04:43:26+08:00

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

回复于 2024-05-14T04:43:26+08:00

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

我想这会更好，更有效 . 请纠正我:) . 谢谢

回复于 2024-05-14T04:43:26+08:00

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)

//要调用上面的函数使用：

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

回复于 2024-05-14T04:43:26+08:00

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

回复于 2024-05-14T04:43:26+08:00

上面有很多好的解决方案，但我还没有看到一个简单的（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

回复于 2024-05-14T04:43:26+08:00

Python中的二进制搜索（二分）

20 回答

基本类型

对象

相关问题