Part 5 — Data Structures and Algorithms in Plain English | Binary Search
Hello! Welcome again. Did you read part 4 of this series? If yes, great! If not, then you need to really do since part 5 will be picking up from there. Don’t worry, I’ve already saved you the stress by including the link to part 4 here https://abbrefy.xyz/part4
In the last part, we started writing an in-depth algorithm to help better explore our knowledge of time complexity. We took it upon ourselves to write an algorithm that will help us search out a number from a list of numbers. And while we were able to implement a solution in the last part, we realized that this solution is not only terrible, it is also time-wasting as every bit of it runs in a Linear Time Complexity. I mean, if we have a list of 500 numbers, and our lost number is in position 490, then it will take use 490 iterations to find this lost number. Now you see why it’s terrible?
How then do we eliminate this? What other way can we employ to write this search algorithm? I mentioned in the last part that by using an algorithm with a Logarithmic Time Complexity, we can make the algorithm way faster such that we can find our lost number in just 9 iterations when the input size becomes 500 elements and even find it in just 20 iterations when the input size is 1,000,000 elements. Such a Logarithmic algorithm is what we call the Binary Search algorithm.
Binary Search is a half-interval search algorithm that finds the position of a specific value within a sorted array.
From the definition above, there are a few things we need to note.
- Binary search doesn’t directly return the value we are searching for rather, it returns its position and we can use this position to locate the value in the array.
- Binary Search can only be used on sorted arrays. This means that if you have a list of numbers, the numbers need to be sorted from the smallest to the largest.
- Binary Search is a half-interval search algorithm which means, for every iteration, it will only search through half of the input data. You will understand this better soon.
Now, let’s start writing our binary search algorithm.
First, we need to specify a high and a low point before starting our search.
In our algorithm above, we have specified nums as the array (list) of numbers we want to search through and we have specified, lost as the number we are looking for.
The low search point will be index 0 and the high search point will be the nth index of our array. We can find this nth index by subtracting 1 from the length of the array itself.
Now, for Binary Search, each time an iteration is made, we divide the array into two (one on the right and one on the left) and then make a guess that the lost number is in the middle of the array.
If this guess is lower than the number, we know that the number can only be in the right array so we update our low search point to become the index of the middle number, however, if this guess is higher than the lost number, then we know that it can only be in the left side of the array so we update our high search point to become the index of the middle number.
Here’s the code for this.
Now, what is left for us is to find a way to re-calculate our mid, guess again, and then repeat the check whether our guess is higher or lower till we find the missing number.
So, how do we go about this? Remember loops? Loops allow us to repeat a block of code over a certain number of iterations. We have both the For loop and the While loop. The For loop requires that we have a defined number of iteration, however, the While loop allows us to run indefinitely.
In our case, we want to keep performing the guess and check operation till our low becomes equal to our high. Here’s the code below.
Now, with this algorithm, we can find any lost number within an array of sorted numbers. However, what if the lost number isn’t present? We need to make sure our code covers that. To do this, we need to return number not found after our while loop.
Here’s how it would look like below.
Now, let’s combine the first part of the algorithm with the second part of the algorithm.
This is great but it won’t work. Remember that return statements are only valid inside of functions? Yes, we need to put our code block inside a function that way we can always reuse it.
And with that comes the final piece of our Binary Search algorithm.
If you want to know how many iterations this will take, you can always tweak the code to allow for that.
But since we know that it uses a Logarithmic Time Complexity, we can always calculate the number of iterations by taking the Log base 2 of n…. where n is our input size.
Welcome to the last iteration of today’s part. Thank you for reading through so far.
If you found this insightful then be sure to clap it loud and if you have any questions don’t hesitate to reach me here https://samperfect.me
See you in the next part of the series.
