Do you know that when we use binary search to locate an item in a sorted array, we can do it in two ways? These two implementations include iterative and recursive methods. Well, algo.monster has a great explanation on binary search implementations. Let’s see how these two approaches of using the binary search algorithm work in this article.
Before we talk about the terminology, let’s explain a little using a simple example.
A simple example of binary search
For example, when we are trying to find a new word from the dictionary, we won’t start from the first page. Say if the word starts with the letter M, we will tend to open the dictionary approximately somewhere around the middle part. If we happen to find L, then we go higher, move on to the right side to locate M.
Now, we find the words that start with the letter M. Suppose the second letter in the word is O. Again, we will try to start from the middle part to the right part of the M section. Obviously, O is in the second half of the alphabet.
What is this search method about?
Binary search algorithms can quickly locate the value of a specified element in a sorted list. And this search technique works on the same principle as the divide and conquer algorithm performs. It is fast but it needs you to sort the data in advance.
You start the search at the center of the array and work your way down to the lower or higher half of the sequence. So, if the element in the middle falls below the target value it means that the search must go higher. Or else, it will continue the search process at the descending portion.
Usually, how the search moves forward depends on the order. In other words, whether to ascend/descend the list based upon the comparison between the target element and the middle one.
However effective it is, a binary search method can only be performed within an ordered set of data. If the data is random, a linear would return results every time. However, a binary search would likely end up in an infinite loop.
Two implementation ways: iterative vs. recursive
Binary search first divides large arrays into smaller sub-arrays just like the divide and conquer algorithm splits subproblems. Then, binary will start the search procedure recursively or iteratively. Because binary search is a progressively dividing algorithm, it requires that the data be in the “sorted form” for the algorithm to work.
Binary search’s iterative and its recursive versions have two major differences.
The recursive version has O(log N) space complexity, while the iterative version is O(1). Even though the recursive option may seem easier to implement, it is still more efficient.
Binary search can either be performed using the iterative algorithm or recursive algorithm. Either way, they may both achieve the same goal.
Iterative algorithm and recursive algorithm
An iterative algorithm uses looping statements to repeat the same steps repeatedly.
A recursive algorithm is a function that calls itself over and over until the base condition (or stopping condition) is met.
Three possible cases are:
If the target you are looking for equals the middle value, it returns to mid.
Then, if the target value tends to be smaller than the middle one, you should eliminate the values that are on the right side of the middle element. Then, you will get the new high:mid-1, and the same low value.
If the target element’s value is higher than the middle, i.e. target>A[mid], then we will discard all values in the left search space. Well, you should also abandon the middle element this time. As a result, the new low should be the middle one plus 1 and the ‘high’ element stays the same.
Iterative binary search
Iterative binary search class’ main() method begins with defining an array of size 6, called A.
The number of elements to search for is key.
Within the while loop, “mid” is obtained by calculating: subtract by 2 the result of low plus high.
If the number at mid position equals key element or target element, the control returns the index for mid element. This is done by printing the number and the index at which it is found.
Elsewhere, if the target value is lower than the middlemost value, then it cuts off the portion array from the mid upwards to contention by making “high” equal to mid-1.
It also implies that the key element is greater than the number at mid (as it isn’t less than and not equal, so it must be higher). Thus, “low” is made equal to “mid+1”. This removes the contention for the part of the list that runs from mid to downwards.
The while loop continues iterating in this manner until the element is either returned or lower is greater than the high. When it is returned, it indicates that it has found the in the array. In these cases, -1 is returned which tells you that the target you want is not even in the array. Then, this is the output.
Recursive binary search
Binary search() recursively implements the binary search algorithm using the method the iterative version uses. Yet, there are a few differences.
The first is that the while loop has been replaced by a callback to the same process with new low and high values passed to the next recursive invoke along with “array” or “key” or target elements.
On the other hand, the fact that instead of returning false if the while loop exits in iterative, in the case of the recursive variant, the condition of low>high is checked at the beginning of the next level in recursion. It acts as a boundary condition and stops further recursive callings by returning false.
Not only that, but the binary search() recursive invokes return the search result up to the recursive calling stack. The true or false return value is returned back up the call stack and not further processing.
Conclusion
Both approaches will have the same O(log n) time complexity. However, they will differ in terms of space use.
Recursive may reach “log(n) space” when the stack occurs, but the iterative version completes “O(1)” space complexity.
For some, recursive codes are easier to understand. However, some people find it difficult to optimize tail recursion.
Therefore, the decision of whether to use recursive or iterative formula is up to the individual and their local preferences.
