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

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

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

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

Answer 2

关于时间复杂度，递归和迭代方法都会给你 O(log n) 时间复杂度，关于输入大小，前提是你实现了正确的二进制搜索逻辑.

关注 space 复杂性，迭代方法更有效，因为我们为函数调用和常量 space 用于变量分配，而递归方法采用 O(log n) space.

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

Recursive and Iterative Binary Search: Which one is more efficient and why?

algorithm

search

pseudocode

time-complexity