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

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

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

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

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

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


当前回答

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

从文档中平分。Bisect_left (a, x, lo=0, hi=len(a))

平分模块不需要预先计算搜索数组。你可以把端点表示为等分线。Bisect_left,而不是使用默认值0和len(a)。

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

只需要提供一个对象,将__getitem__定义为

例如,我们可以使用平分算法以任意精度找到一个平方根!

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)

其他回答

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

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

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

你好,这是我的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找到在给定的排序范围内插入元素的第一个位置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

二分查找:

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