Binary Search - Why use Iterative over Recursive approach?
Whether we are starting to learn a new language or preparing for our first college placement or interview, we all have learned and implemented Binary Search in our lives.
Before moving forward let us go over the basics of Binary Search.
In Binary Search, we divide the array from the middle and compare the element to be searched against the middle element. If the element is less than the middle we narrow the search interval to the first-half otherwise narrow the interval to the second half. We follow this process repeatedly until the element is found or the interval is empty.
Binary Search follows a Divide and Conquer technique to find the required element in a given list of sorted elements.
Now we are aware of the fact that Binary search takes advantage that the array is sorted and reduces the time complexity to O(logn).
But do we also consider space complexity while implementing a Binary search?
Even though the Recursive approach is much easier to understand and implement and has the same time complexity as the Iterative approach, the Space complexity is higher in the case of Recursive Binary search, which is O(logn) as compared to O(1) in the case of Iterative Binary Search.
The recursive approach may seem like an easy and concise way of writing code and the processor eventually model it like a loop, but it stores the call to the function every time in a call stack which ends up taking logn of space for n number of times a function is called where n = total number of items in the dataset.
In the end, it is really a matter for individual decision to choose how to implement a Binary Search but to keep some key things in mind about Recursive and Iterative Binary Search
- Both have a time complexity of O(logn).
- Recursive BS has a space complexity of O(logn).
- Recursive BS store function calls in a call stack.
- Recursive BS is easy to approach and maintain.
We have come to the end of the article and I hope you learned something new today, and I look forward to learning something from you.
Clap, Share and Follow if you like the content.
Ciao, Hasta Luego!