algorithm - 递归和迭代二进制搜索 : Which one is more efficient and why?

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(log n) 时间复杂度，关于输入大小，前提是你实现了正确的二进制搜索逻辑。

着眼于空间复杂度，迭代方法更有效，因为我们为函数调用分配了常量 O(1) 空间，为变量分配了常量空间分配，而递归方法占用 O(log n) 空间。