如果找不到该项目，我该如何进行此偏移二进制搜索 return None？

Question

我必须使用偏移量进行二分查找，所以没有左变量或右变量。如果找不到该项目，我需要将其设置为 return 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

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

正如所写，您的函数将始终 return 一个整数，因为 mid + offset 是一个整数。如果你想 return 一个 None，你将需要一个空的 return 某处（if/elif/else 链永远不会跌倒）。
您需要在某处为递归设置停止条件。您目前确实有一个（在评论 "if the item is at mid, we're done" 之后）。但是，您将需要另一个不同的 return 来处理值不存在的情况。
如果您收到一个空数组作为输入，mid 将被计算为索引 0。这样看起来对吗...？
切片 array[mid:] 包括索引 mid 处的项目。在 array[:mid] 处切片不包含索引 mid 处的项目。在 if/elif/else 的三个分支中寻找任何逻辑重叠。

如果找不到该项目，我该如何进行此偏移二进制搜索 return None？

How can I make this offset binary search return None if the item is not found?

python

binary-search

offset