这个二分查找函数的递归关系是什么？

Question

我正在看这个多项选择题：

写出下列函数的递推关系。

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)
⦿  这些都不是

我认为答案是“都不是”。我认为，因为您使用索引执行二分搜索，所以数组不会减半或以任何方式更改，因此从技术上讲，每次调用函数时问题大小都保持不变。

如有任何意见，我们将不胜感激。

Answer 1

...数组不会以任何方式减半或更改，因此从技术上讲，每次调用函数时问题大小都保持不变。

这不是真的：虽然整个数组在每次调用时都可用，但实现的逻辑只会访问

low

-

high

范围内的值，因此问题大小确实是

high-low+1

。

因此，有一个选项是正确的。

T(𝑛) = T(𝑛/2) + O(1)

Answer 2

你必须小心

n

是什么。它不是数组的大小。它是由 low 和

high

定义的

interval

的大小，在本例中为

n = high - low - 1

。

每个调用都在特定的时间间隔上进行操作，该时间间隔用于关注

arr

的特定子数组。递归调用始终使用一对

(low', high')

进行，其中保证满足以下条件之一：

1. low < low'

2. high' < high

只要这是真的，隐含值

n' = high' - low' + 1 < n

保证递归最终将达到

n <= 0

的基本情况，由

low > high

在代码中检查（相当于

low - high > 0

或

high - low < 0 == high - low + 1 <= 0

。

所以，从技术上来说，

T(n)

并不是用

len(arr) == n

解决问题所需的时间，而是用

high - low + 1 == n

解决问题所需的时间。

mid

的定义及其用于定义

low'

或

high'

确保每个问题的

n

减半。