python - 如果找不到该项目，如何使此偏移二分搜索返回 None？

Question

我必须使用偏移量进行二进制搜索，因此没有左变量或右变量。如果找不到该项目，我需要让它返回 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

我尝试了很多不同的东西，但我似乎无法弄明白。谢谢!

Answer 1

观察这些事实并使用它们来调整您的算法:

• 正如所写，您的函数将始终返回一个整数，因为 mid + offset 是一个整数。如果你想返回一个None，你需要在某处有一个简单的return(if/elif/else 链永远不会失败)。
• 您需要在某处为递归设置停止条件。您目前确实有一个(在评论“如果项目在中间，我们就完成了”之后)。但是，您将需要另一个不同的return 来处理值不存在的情况。
• 如果您收到一个空数组作为输入，mid 将被计算为索引 0。这样看起来对吗...？
• 切片 array[mid:] 包括索引 mid 处的项目。在array[:mid] 处切片不 包括索引mid 处的项目。在 if/elif/else 的三个分支中寻找任何逻辑重叠。