递归算法伪代码

Question

我想创建一个将以 O(logn) 复杂度执行的递归伪代码 我希望它找到较低的 f(i) < 0 和 f[1....n] 其中 f(1) >0 和 f(n)<0

prodedure fanc(A[n] , p , q )  //(this is my array,first digit of A ,last digit of A)
if A[n/2] >= 0
     return fanc(A[n/2] , A[n/2] , A[n-1])
else
     return fanc(A[n/2] , A[0] , A[n/2 -1])
if p<q
   print p
else
   print q

我知道我必须以某种方式结束递归。另外我想知道我是否走在正确的道路上，以及您是否对这个问题有什么好的想法！

---

从复制的更好的作业文本：

Let an integer function f:{1,2,3...n} be monotonic and defined in {1,2,3...n} and suppose that f(1) > 0 and f(n) < 0. We would like to find the smallest integer i with f(i) < 0. Design an algorithm for this purpose that run in O(logn).

Answer 1

你快到了，你必须让它相对于 p 和 q（从和到）而不是 n。然后如果从 == 到你找到了解决方案。这假设在 [1 ... n].

范围内始终存在解决方案

function firstNegative(f, from, to) {
    if (from == to)
        return from;
    next = from + (to - from) / 2;
    if (f(next) >= 0)
        return firstNegative(f, next + 1, to);
    else
        return firstNegative(f, from, next);
}
print firstNegative(f, 1, n);