python中的二进制搜索算法 [英] Binary search algorithm in python

问题描述

我正在尝试在python中实现二进制搜索，并将其编写如下。但是，无论何时needle_element大于数组中的最大元素，我都无法停止它。

I am trying to implement the binary search in python and have written it as follows. However, I can't make it stop whenever needle_element is larger than the largest element in the array.

可以帮忙吗？

def binary_search(array, needle_element):
    mid = (len(array)) / 2
    if not len(array):
        raise "Error"
    if needle_element == array[mid]:
        return mid
    elif needle_element > array[mid]:
        return mid + binary_search(array[mid:],needle_element)
    elif needle_element < array[mid]:
        return binary_search(array[:mid],needle_element)
    else:
        raise "Error"

推荐答案

如果 needle_element> array [mid] ，您当前将 array [mid：] 传递给递归调用。但是您知道 array [mid] 太小，因此您可以通过 array [mid + 1：] （并相应地调整返回的索引。）

In the case that needle_element > array[mid], you currently pass array[mid:] to the recursive call. But you know that array[mid] is too small, so you can pass array[mid+1:] instead (and adjust the returned index accordingly).

如果指针大于数组中的所有元素，则这样做最终将为您提供一个空数组，并且

If the needle is larger than all the elements in the array, doing it this way will eventually give you an empty array, and an error will be raised as expected.

注意：每次创建子阵列都会导致大型阵列的性能下降。最好改为传递数组的边界。

Note: Creating a sub-array each time will result in bad performance for large arrays. It's better to pass in the bounds of the array instead.

这篇关于python中的二进制搜索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！