该二分查找函数的递推关系式是什么？我的判断是否正确？

写出以下函数的递推关系式。

def b(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return b(arr, target, low, mid - 1)
    else:
        return b(arr, target, mid + 1, high)

选项： #

• ⵔ 𝑇(𝑛) = 2𝑇(𝑛/2) + O(1)
• ⵔ 𝑇(𝑛) = 𝑇(𝑛/2) + O(1)
• ⵔ 𝑇(𝑛) = 2𝑇(𝑛−1) + O(1)
• ⵔ 𝑇(𝑛) = 2𝑇(𝑛/2) + O(𝑛)
• ⵔ 𝑇(𝑛) = 4𝑇(𝑛/4) + O(1)
• ⦿ None of these

我认为答案是“None of these”，理由是该二分查找通过索引实现，数组并未被拆分或修改，因此严格来说每次调用时问题规模并未改变，希望得到大家的意见。

内容的提问来源于stack exchange，提问作者velzzz