Algorithms are a set of instructions for accomplishing tasks. In this post, we'll look at one of the simplest algorithms - binary search.
When I was in primary school. Each day before our classes, we would line up in a straight line according to our heights in the morning assembly.
The headteacher would have the shorter students lined up in front and the taller ones at the back.
This ensures that everyone sees the podium as he doles out instructions for the day.
Imagine you landed mysteriously in this gathering, and you were given a task to pick the tallest student or the shortest student on the line. How easy do you think this would be? I assume, very easy.
Why? Because you know the section where he would be located. You don't have to compare each student with one another before you locate the tallest student.
Now let's switch the scenarios around a bit. If the students lined up randomly without following a specific order. I guess it would not only be time-consuming; you would also have to make some comparisons before you find him.
Worst case scenario, you would pick one student at a time, compare him with the other, and repeat the process until the last one. This is known as linear search and it has a worst-case scenario of O(N).
Now, in programming context, assuming you were given an ordered list of numbers as follows:
const numbers = [1, 3, 5, 9, 10, 13, 14, 17, 19]
If you are asked to find the position (index) of 17 in the list, you could do a quick scan with your eyes and see it at the right end.
Yeah, quite easy! But in a computer's world, things are a bit different. It doesn't have physical eyes like us. It has to make some comparisons to find it.
Time is money, and whatever comparison techniques your code employs, you better be sure it's a technique that saves time. This is why the binary search algorithm is essential.
How Binary Search Works
Binary search is an algorithm that limits the number of comparisons your program has to make before it can find an item in an ordered array.
For you to apply a binary search, your list must be ordered. In other word, it must be sorted.
We can represent the list in the previous example in a computer memory as this:
The first step would be to find the midpoint of the list. We can do this by dividing the size of the array by 2.
Once you know the midpoint, you can quickly get the region of the array where the "search value" will be located.
We can see that the value in the middle of the list is 10.
Since 17 is higher than the value in the middle ( that is, 10), we understand that the value we're looking for will be at the right side of the list.
We compute mid-value at the right-hand side again and compare it with 17.
This process of comparing and discarding is repeated until a match is found.
Let's represent this process in code:
function binarySearch(orderedList, search) {
let highIndex = orderedList.length - 1;
let lowIndex = 0;
while (lowIndex <= highIndex) {
let midIndex = Math.floor((highIndex + lowIndex) / 2);
if (orderedList[midIndex] === search) {
return midIndex;
} else if (search > orderedList[midIndex]) {
lowIndex = midIndex + 1;
} else {
highIndex = midIndex;
}
}
return false;
}
We use lowIndex and highIndex to keep track of which part of the list to search.
We took advantage of the fact that at one point, lowIndex will be higher than highIndex. We wrap it in a while loop to keep searching the part the value will be in and eliminating the other half in the process.
We can test the code as:
const numbers = [1, 3, 5, 9, 10, 13, 14, 17, 19];
console.log(binarySearch(numbers, 17)); // 7
Time Complexity
In each loop, half of the list is eliminated. This saves a lot of time compared to a linear search. The worst-case scenario for an ordered list of 8 items would take 3 guesses.
If we double the size of the list, the worst-case scenario takes 4 guesses. Hence binary search runs in logarithmic time O(logN).