这个函数的递推关系是什么？

Question

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

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

Answer 1

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

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

low

-

high

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

high-low+1

。

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

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