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

Question

I have written the algorithms for recursive and iterative binary search:

Recursive

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);
    } 
}

Iterative

// 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;
}

Which one of them will be more efficient and how does one find that. Should count statements be added to count number of steps in each and based on that can efficiency be determined?

You need to define "efficient" for your application. I've had real-life applications in which bubble sort and linear search were more efficient due to the overhead of extra variables, or implementation, or maintenance. — Prune, Aug 13 '19 at 16:58
If you're wondering about computational complexity, see [here](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it). If you want actual compute time, use your system's timing facility and run large test cases. If you're unsure about the iteration / recursion mechanics, insert a couple of strategic `print` statements to show you the data and control flow. — Prune, Aug 13 '19 at 17:00
One thing with iterative method is that the internal stack needn't popped out after every call. — SomeDude, Aug 13 '19 at 17:02

score 22 · Answer 1 · edited May 02 '22 at 13:55

22

With regard to time complexity, recursive and iterative methods both will give you O(log n) time complexity, with regard to input size, provided you implement correct binary search logic.

Focusing on space complexity, the iterative approach is more efficient since we are allocating a constant amount O(1) of space for the function call and constant space for variable allocations, while the recursive approach takes O(log n) space.

edited May 02 '22 at 13:55

pommy

3,717
1
15
25

answered Aug 13 '19 at 17:38

Peter

2,796
1
17
29

2

Nice one. I was looking for the space complexity answer. Thanks bro – Hugo Nava Kopp Feb 17 '21 at 18:12

score 9 · Accepted Answer · answered Aug 13 '19 at 17:28

There is no different w.r.t Big O analysis between these two versions. Both will run O(logn) if written correctly.
There have been concerns around the recursive program regarding the function stack it is going to use. However, once you see it carefully, the recursive version is a tail recursion. Most of the modern compiler converts the tail recursion into iterative program. Thus, there won't be any issue regarding the usage of the function stack.
Hence, both will run with same efficiency.

Personally, I like the recursive code. It is elegant, easy and maintainable. Binary search is a notoriously difficult algorithm to implement correctly. Even, java library had bug in the implementation.

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

2 Answers2