用二进制搜索法求最接近值的索引

Question

我想用python进行二进制搜索：

def binarySearch(data, val):

其中，data是排序数组，value是要搜索的值。如果找到值，我想返回index（这样data[index] = val）。如果找不到该值，则返回最接近该值的项的index。

以下是我所得到的：

def binarySearch(data, val):
    high = len(data)-1
    low = 0
    while True:
        index = (high + low) / 2
        if data[index] == val:
            return index
        if data[index] < val:
            low = index
        if data[index] > val:
            high = index

Answer 1

我知道这是一个老问题，但它对谷歌的结果很重要，我也有同样的问题。有一个内置的这样做，它使用二进制搜索，并允许您在一个引用数组和一个比较数组饲料。

numpy.searchsorted(a, v, side='left', sorter=None)

a是引用数组（data在原始问题中），v是要比较的数组（val在问题中）。这将返回一个具有int值的array大小v索引，需要将v的第n个元素插入a中以保留a中的排序顺序，side关键字确定是否要将v的元素放在a中的适当值的“左”（前）或“右”（后）。

[截至2017年7月的文档链接] https://docs.scipy.org/doc/numpy/reference/generated/numpy.searchsorted.html#numpy.searchsorted

Answer 2

像这样的事情应该行得通。它返回一个包含两个索引的数组。如果找到val，则返回数组中的两个值都相同。否则，它将返回最接近val的两个项的索引

def binarySearch(data, val):
    highIndex = len(data)-1
    lowIndex = 0
    while highIndex > lowIndex:
            index = (highIndex + lowIndex) / 2
            sub = data[index]
            if data[lowIndex] == val:
                    return [lowIndex, lowIndex]
            elif sub == val:
                    return [index, index]
            elif data[highIndex] == val:
                    return [highIndex, highIndex]
            elif sub > val:
                    if highIndex == index:
                            return sorted([highIndex, lowIndex])
                    highIndex = index
            else:
                    if lowIndex == index:
                            return sorted([highIndex, lowIndex])
                    lowIndex = index
    return sorted([highIndex, lowIndex])

Answer 3

下面是找到值时将返回索引的代码，否则是最接近该值的项的索引，希望能有所帮助。

def binarySearch(data, val):
    lo, hi = 0, len(data) - 1
    best_ind = lo
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if data[mid] < val:
            lo = mid + 1
        elif data[mid] > val:
            hi = mid - 1
        else:
            best_ind = mid
            break
        # check if data[mid] is closer to val than data[best_ind] 
        if abs(data[mid] - val) < abs(data[best_ind] - val):
            best_ind = mid
    return best_ind

def main():
    data = [1, 2, 3, 4, 5, 6, 7]
    val = 6.1
    ind = binarySearch(data, val)
    print 'data[%d]=%d' % (ind, data[ind])

if __name__ == '__main__':
    main()