使用切片的二进制搜索实现

Question

关于下面给出的二进制搜索实现：

def bin_search(arr, key):
    n = len(arr)
    if n < 2:
       return (0 if (n == 1 and arr[0] == key) else None)
    m = int(0.5 * n)
    if arr[m] > key:
       return bin_search(arr[:m], key)
    result = bin_search(arr[m:], key)
    return (result + m if result != None else None)

对于上面的二进制搜索实现，时间复杂度会受到影响，因为我们正在获取数组的切片，space 复杂度也会受到影响，因为 python 中的列表切片会创建一个新的列表对象。为了改进上述实现，我正在考虑像在其原始实现中一样引入下限和上限变量。但是会完全修改上面的代码实现。

能否请您告诉我如何修改上述实现，以便改进它的时间和 space 复杂性，我对其复杂性的理解是否正确？

Answer 1

这是时间复杂度 O(log(n)) 和 space 复杂度 O(1) 的迭代解决方案。您无需修改数组，而只需修改指针的位置。我指的是 left/right 指点。

def binary_search(array, target):
    return binary_search_helper(array, target, 0, len(array) - 1)


def binary_search_helper(array, target, left, right):
    while left <= right:
        middle = (left + right) // 2
        match = array[middle]

        if target == match:
            return middle
        elif target < match:
            right = middle - 1
        else:
            left = middle + 1

    return -1

递归解决方案：我没有看到通过轻微更改来提高复杂性的方法，因为您需要使用位置数组本身。这将影响您的基本情况和函数调用。这是我将 space 复杂度从 O(n) 降低到 O(log(n)) 的尝试。

def bin_search(arr, key, left=0, right=len(arr) - 1):
    # Should change base case since we modify only pointers
    if left > right:
        return None

    # since we are not modifying our array working with length will not work
    m = int(0.5 * (left + right))

    if arr[m] == key:
        return m
    elif arr[m] > key:
       return bin_search(arr, key, left, m - 1)
    else:
        return bin_search(arr, key, m + 1, right)

PS：需要预先创建arr或创建另一个调用函数，因为我们在函数定义中定义了right=len(arr) - 1。我建议使用这样的调用函数：

def binary_search_caller(arr, key):
    return bin_search(arr, key, 0, len(array) - 1)

并将函数定义更改为：

def bin_search(arr, key, left, right):
    ...

使用切片的二进制搜索实现

Binary Search Implementation Using Slicing

python

algorithm

binary-search

time-complexity