Menu
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?
736
Iteration is faster and more efficient than recursion. It's easier to optimize iterative codes, and they generally have polynomial time complexity. They are used to iterate over the elements present in data structures like an array, set, map, etc.
Iterative algorithms and methods are generally more efficient than recursive algorithms. Recursion is based on two key problem solving concepts: divide and conquer and self-similarity. A recursive solution solves a problem by solving a smaller instance of the same problem.
The major difference between the iterative and recursive version of Binary Search is that the recursive version has a space complexity of O(log N) while the iterative version has a space complexity of O(1). Hence, even though recursive version may be easy to implement, the iterative version is efficient.
Recursion is usually slower than iteration due to the overhead of maintaining the stack. Recursion uses more memory than iteration. Recursion makes the code smaller.
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.
126
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.
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
