python中的二进制搜索算法

本文介绍了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.