我必须使用偏移量进行二进制搜索,因此没有left或right变量。如果找不到该项目,我需要使其返回None,但是由于某种原因,我对如何做到这一点感到困惑。我知道你能做
if right >= left:
#search function here
else: return None
但是我没有这些变量,并且不适用于array [mid:]> = array [:mid]
这是功能
def binary_search(array, item, offset=0):
mid = int(len(array)/2) #make mid an int so it truncates
if item == array[mid]: #if the item is at mid, we're done
return mid + offset
elif item > array[mid]: #if the item is bigger than the item at mid, go to right side of array
return binary_search(array[mid:], item, offset+mid) #add the mid value to offset since we're going right
else: #otherwise, the value is smaller and we go to the left side of the array
return binary_search(array[:mid], item, offset) #leave offset the same
我尝试了很多不同的方法,但似乎无法弄清楚。谢谢!
最佳答案
观察这些事实,并使用它们来调整算法:
如所写,您的函数将始终返回整数,因为mid + offset
是整数。如果要返回None
,则在某个地方需要裸露的return
(if
/ elif
/ else
链永远不会掉线)。
您需要在某个地方停止递归。您当前有一个(注释“如果项目在中间,我们就完成了”)。但是,当值不存在时,您将需要另一个不同的return
来处理这种情况。
如果您收到一个空数组作为输入,则mid
将被计算为索引0。这看起来是否正确...?
切片array[mid:]
包括索引为mid
的项目。在array[:mid]
处切片不包括索引在mid
处的项目。在if / elif / else的三个分支中查找任何逻辑重叠。