我正在尝试用 python 实现二分搜索,并将其编写如下。但是,只要needle_element大于数组中的最大元素,我就无法让它停止。
你能帮我吗?谢谢。
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
and upper
索引为莱塞诉卡尔森在对该问题的评论中提出建议。
这将是代码:
def binary_search(array, target):
lower = 0
upper = len(array)
while lower < upper: # use < instead of <=
x = lower + (upper - lower) // 2
val = array[x]
if target == val:
return x
elif target > val:
if lower == x: # these two are the actual lines
break # you're looking for
lower = x
elif target < val:
upper = x
-
lower < upper
一旦您到达较小的数字(从左侧开始),就会停止
-
if lower == x: break
一旦您达到更高的数字(从右侧)就会停止
Example:
>>> binary_search([1,5,8,10], 5) # return 1
1
>>> binary_search([1,5,8,10], 0) # return None
>>> binary_search([1,5,8,10], 15) # return None
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)