Part 7 — Data Structures and Algorithms in Plain English | Recursive Binary Search
I really have to say apologies for going off for so long and thank you so much to everyone who has been consistently following this series so far. I want to believe a lot of us have benefitted in a way or the other from these articles.
In Part 5 and Part 6 of the series, we learned about Binary Search and Recursion respectively. We discussed a lot of concepts regarding each topic but what we did not talk about, however, is how these two go hand in hand with each other.
Remember our final codebase from the Binary Search algorithm we wrote in Part 5? It’s okay if you don’t…I already attached it below for you to remember. However, be sure to go back to check Part 5 again for better understanding.
Notice how we made use of a While statement to keep our code running till the lost number is found?
Good! Now if you can remember from our explanation of Recursion, we said that…
Recursion can be defined as a process whereby a function calls itself directly or indirectly until it no longger needs to.
And following from the While statement usage above, we are simply calling a specific code block over and over again until we find our lost number. This means that rather than make use of a While statement to control how the code is being called, we can simply take advantage of Recursion.
To make our Binary Search recursive we need a base case to help stop the call when the lost number is found. The base case would be the same as the condition we used in the While statement.
Next, we need to take control of the high and low points which means we need to define them outside of the function. Putting this all together, we have…
You might be wondering why we had to put the high and low as variable outside of the function… this will become clear in a minute.
Now, that we have the base case sorted out, the next is to check whether we have found our number just like we did in the previous implementation.
Now, that we have control over how to stop our code when we find the lost number, it’s time to take advantage of Recursion for cases where the guess is too high or too low.
When the guess is greater than the lost number, we shit to the left subarray as usual but this time, we call the function again (recursive) and pass in the lost, low, and new high value. And when the guess is lower than the lost number, we shift to the right subarray, make a recursive call, and pass in the lost, high, and new low value. With the previous knowledge of recursion, call stack, memory, all, you should be able to figure out what is going on in this recursive flow.
Finally, we need to stop our algorithm from running if the number could not be found. And with this, we have our final code as…
And there you go! A fully functional Recursive Binary Search algorithm. Now that we have sorted this out. The next article will focus on how we can use Binary Search to find a specific word from an array of sorted words.
Stay tuned for that! 😎
If you want to reach me either for questions, consultation, or work purposes, you can do that via https://samperfect.me
Stay safe and goodbye 👋
