正确的二进制搜索算法

Question

下面这样写一个二分查找的实现可以吗？

    def binarySearching(sortedArr,v):
    if len(sortedArr)>=1:
        mid = len(sortedArr)//2
        if v<sortedArr[mid]:
            return binarySearching(sortedArr[:mid],v)
        elif v>sortedArr[mid]:
            return binarySearching(sortedArr[mid+1:],v)
        else:
            return mid
        return None

不明白为什么要指定low和high 为算法。

编辑：感谢@Stef，此实现不正确，因为 mid 不是原始数组，而是子数组

Answer 1

当您使用唯一的 array/list 时，您必须指定 low and high 。在每次迭代中，您都会处理 low..high 范围内的列表的一部分。

您的实现生成了子列表，因此不需要明确的范围定义（但是这个子列表的形成是免费的吗？）

Answer 2

使用二进制搜索算法时，每一步都会将搜索范围缩小一半。

您指定 low 和 high，因为您传递相同的数组进行搜索并仅更改搜索区域。

传递 low 和 high 的替代方法是传递数组的一部分，但在 python 中，这意味着每次切片数组（列表）时都会创建另一个对象（这是切片列表）-内存效率低下。

Answer 3

比较binarySearch的这两个实现。第一个是你的，第二个是我的

在您的版本中，您正在将“切片”（即子数组的完整副本）传递给递归调用。在我的版本中，所有递归调用都访问同一个数组而不复制它，而是仅将 low 和 high 作为参数传递。

# using slices, ie, copies of subarrays
def binarySearching(sortedArr,v):
    # print(sortedArr)
    if len(sortedArr)>=1:
        mid = len(sortedArr)//2
        if v<sortedArr[mid]:
            return binarySearching(sortedArr[:mid],v)
        elif v>sortedArr[mid]:
            return binarySearching(sortedArr[mid+1:],v)
        else:
            return mid
    else:
        return None

# using low and high indices
def otherBinarySearching(sortedArr, v):
    def auxiliary(low, high, v):
        #print(low, high, sortedArr[low:high])
        if high > low:
            mid = (high + low) // 2
            if v < sortedArr[mid]:
                return auxiliary(low, mid, v)
            elif v > sortedArr[mid]:
                return auxiliary(mid+1, high, v)
            else:
                return mid
        elif high == low:
            return (low if v == sortedArr[low] else None)
    return auxiliary(0, len(sortedArr), v)

# add some tests to make sure implementations are correct
if __name__=='__main__':
    a = [x for x in range(0, 101, 2)]
    b = [x for x in range(1, 100, 2)]
    print('a: ', a)
    print('b: ', b)
    print('binarySearching:      ', all(isinstance(binarySearching(a, x), int) for x in a) and all(binarySearching(a, x) is None for x in b))
    print('otherBinarySearching: ', all(otherBinarySearching(a, x) == x / 2 for x in a) and all(otherBinarySearching(a, x) is None for x in b))

此外，您的版本 returns 索引错误：行 [=14=] returns 子数组 binarySearching 当前正在查看的 v 的索引，而不是原始数组中的索引。

正确的二进制搜索算法

Correct binary-search algorithm

python

algorithm

binary-search