递归和迭代二分搜索：哪个更有效，为什么？

Question

我已经编写了递归和迭代二进制搜索的算法：

递归

AlgorithmBinSrch(a, i,l,x)
// Given an array a[i :l] of elementsin nondecreasing
// order,1<i <=l,determinewhetherx is present,and
// if so,return j suchthat x = a[j];elsereturn 0.
{
    if (l =i) // If Small(P) {
        if(x=a[i]) 
            return i;
        else 
            return 0;
    } else { // ReduceP into a smallersubproblem.
        mid:=[(i+l)/2]; 
        if (x = a[mid]) 
            return mid;
        else if (x <a[mid]) 
            returnBinSrch(a,i,mid-1,x);
        else
            returnBinSrch(a,mid1+,l,x);
    } 
}

迭代

// Given an array a[1:n] of elementsin nondecreasing
// order,n >=0,determine whether x is present,and
// if so,return j suchthat x = a[j];elsereturn 0.
{
    low :=1;high :=n;
    while (low<=high) {
        mid:= [(low+high)/2];
        if (x <a[mid])
            high :=mid-1;
        else if (x >a[mid])
            low :=mid+ 1;
        else 
            return mid;
    } 
    return 0;
}

其中哪一个会更有效率，以及如何找到这一点。是否应该count添加语句来计算每个步骤中的步骤数并基于此确定效率？

Answer 1

这两个版本之间没有不同的大 O 分析。O(logn)如果写入正确，两者都会运行。
关于递归程序将使用的函数堆栈一直存在担忧。然而，一旦你仔细看到它，递归版本是一个尾递归。大多数现代编译器将尾递归转换为迭代程序。因此，函数堆栈的使用不会有任何问题。
因此，两者都将以相同的efficiency.

就个人而言，我喜欢递归代码。它优雅、简单且可维护。二分搜索是众所周知的难以正确实现的算法。甚至，java 库在实现中也有错误。

Answer 2

关于时间复杂度，递归和迭代方法都会为您提供O(log n)时间复杂度，就输入大小而言，前提是您实现了正确的二分搜索逻辑。

关注空间复杂度，迭代方法更有效，因为我们O(1)为函数调用分配了恒定量的空间，为变量分配分配了恒定空间。