我必须使用偏移量进行二进制搜索,因此没有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,则在某个地方需要裸露的returnif / elif / else链永远不会掉线)。
您需要在某个地方停止递归。您当前有一个(注释“如果项目在中间,我们就完成了”)。但是,当值不存在时,您将需要另一个不同的return来处理这种情况。
如果您收到一个空数组作为输入,则mid将被计算为索引0。这看起来是否正确...?
切片array[mid:]包括索引为mid的项目。在array[:mid]处切片不包括索引在mid处的项目。在if / elif / else的三个分支中查找任何逻辑重叠。

09-17 13:16
查看更多