我试图用python实现二进制搜索,并编写如下。但是,每当针元素大于数组中最大的元素时,我无法使其停止。
你能帮忙吗?谢谢。
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"
使用
lower
和upper
索引会更好,因为Lasse V.Karlsen在对这个问题的评论中建议使用。这就是代码:
lower < upper
到达较小的数字(从左侧)后将停止if lower == x: break
到达较高的数字(从右侧)后将停止示例:
在
needle_element > array[mid]
的情况下,当前将array[mid:]
传递给递归调用。但是你知道array[mid]
太小了,所以你可以通过array[mid+1:]
(并相应地调整返回的索引)。如果指针比数组中的所有元素都大,这样做最终会得到一个空数组,并且会像预期的那样产生错误。
注意:每次创建子数组都会导致大型数组的性能下降。最好是在数组的边界中传递。
为什么不使用对分模块呢?它应该完成你所需要的工作——更少的代码供你维护和测试。
相关问题 更多 >
编程相关推荐