我想创建一个递归伪代码，它将以 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
我知道我必须以某种方式结束递归。我也想知道我是否在正确的道路上，如果你对这个问题有什么好的想法！
从https://stackoverflow.com/questions/42935621/algorithm-in-ologn复制的更好的作业文本：
设一个整数函数 f:{1,2,3...n} 是单调的并在 {1,2,3...n} 中定义，并假设 f(1) > 0 且 f(n) < 0。我们想找到 f(i) < 0 的最小整数 i。为此设计一个运行在 O(logn) 中的算法。
你快到了，你必须让它相对于 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);
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句