Getting Started With Algorithms — Binary Search
Ahh, Algorithms. The subject of a million software development interview questions. If you are a software developer, then chances are, you’ve probably heard about algorithms.
If you haven’t then no worries. The Pandora FMS blog has a great intro about what they are and how they’re applicable in your day to day activities as a developer. The short definition of an algorithm is that it’s a finite set of steps on how to solve a particular problem.
Okay now that we know what an algorithm is, let’s talk about one of the most popular ones ever — The Binary Search Algorithm. Put simply, Binary Search is an algorithm that helps you search through sorted lists in O(log n) time.
O(log n) is just the worst possible time a Binary Search algorithm takes to find a value in a sorted list. For more information about O(log n), check out CS Dojo’s awesome video on Big O Notation.
We now know what the Binary Search Algorithm is, let’s look at how it actually works and how we might implement it in JavaScript.
Awesome! Time to get into the nitty-gritty of good ol’ Binary Search.
Say you wanted to find the 12th item in a menu of 20 items. You’d most likely just jump straight to the middle of the menu and go down two places. That was pretty easy for you but would a computer find the item that way?
No, because computers are stone dumb.
They have no intuition that the 12th item is somewhere in the middle of the menu (or any intuitions at all). For a computer to find that 12th item, it would have to start at the beginning and check every item until it finds it.
Now that approach isn’t all that bad for very small amount of data. However, suppose we weren’t looking through a menu of 20 items. Imagine if we were looking for the word ‘jumper’ in a list of 2 million sorted English words.
It would become terribly inefficient for the computer to go over every word in the list until it finds ‘jumper’. What if ‘jumper’ was number 1,500,000 in the list? It would take the poor computer 1.5 million steps to get it. There has to be a better way.
There is! Let’s approach that same problem using the Binary Search algorithm.
How about instead of going through each word in the list, we just jump to the middle of the list and check if the word in the middle of the list is ‘jumper’. If it isn’t, well, does ‘jumper’ come before or after the word in the middle of the list?
If it comes before, then we know that ‘jumper’ couldn’t possibly be found on the right side of the middle word. Well, that means the right side of the middle word is now useless to us. Let’s throw it away and repeat what we just did with all the items to the left of the middle word.
For those of us keeping count, we have now reduced our list from 2 million to 1 million with just one step. So if we repeated the above process with the remaining million words, we would either find ‘jumper’ or we would throw away another half of the list.
We just keep repeating this process until we’re left with just 1 word which, if we followed the process religiously, would be ‘jumper’.
So to recap, with Binary Search, we’ll only need 21 steps at worst to find a value in a list of 2 million entries. That’s a pretty significant upgrade from our first approach.
Enough talk! Let’s look at the pseudocode for this.
Begin1. Jump to the middle of the list
2. is the item here our item?
3. yes? stop here and return the item
4. no? does our item come before this current item?
5. yes? go back to step 1 using only the left side of the item
6. no? go back to step 1 using only the right side of the itemEnd
That is all there is to Binary Search really. We just keep repeating the above process until we find our item.
We now have all we need to write the actual code to implement this.
1 function binarySearch(array, target) {
2 let left = 0;
3 let right = array.length - 1; // because arrays start at 0
4 let count = 0;
5
6 while (left <= right) {
7 count += 1;
9 const middle = Math.floor((left + right) / 2);
10
11 if (array[middle] === target) {
12 return `Found ${target} in ${count} tries.`;
13 }
14
15 if (target > array[middle]) {
16 left = middle + 1;
17 } else {
18 right = middle - 1;
19 }
20 }
21
22 return 'Could not find target';
23 }Sweet beautiful code! Let’s walk through it.
2 let left = 0;
3 let right = array.length - 1; // because arrays start at 0
4 let count = 0;So right at the beginning, we’re declaring three variables. left is going to be initialized to 0 for now, rightis going to be initialized to the length of the array, and countis just to record how many times the algorithm ran to find the target value.
6 while (left <= right) {We need a while loop to help us repeat the algorithm as many times as needed. Why is the condition set to left <= right though?
Well, we want the while loop to terminate when there’s only one value left in the array. Since we’re splitting the array in half every time the algorithm iterates, we’re eventually going to be left with only one value. At this point left will hold the same value as right and the while loop will end.
7 count += 1;
9 const middle = Math.floor((left + right) / 2);Moving on! Inside the while loop, we’re just incrementing our counter by one every time the loop runs (not integral to the algorithm). Then we’re declaring a variable middle to hold the current middle index of the array every time we divide the array by half.
11 if (array[middle] === target) {
12 return `Found ${target} in ${count} tries.`;
13 }We then check if the value at the middle of the list is what we’re looking for. If it is, end the algorithm and return both the value and the number of times the loop iterated to get this value.
15 if (target > array[middle]) {
16 left = middle + 1;
17 }If we didn’t find our value, however, we’ll check if our target value is greater than the value at the middle of the array and if yes, update our left variable accordingly. This means we just threw away the left side of our array since all the values to the left are automatically less than our target value.
17 else {
18 right = middle - 1;
19 }If our target value is less than the value at the middle of the array, we’ll update our right variable accordingly, effectively throwing away the right side of the array since all the values to the right are automatically greater than our target value.
22 return 'Could not find target';At this point, the loop will keep repeating until we’re left with just one value which is most likely our value. If our value does not exist in the array, the last return statement will be executed and the program will terminate.
Congratulations! We just implemented Binary Search from scratch. Here’s a CodePen sandbox to play with to help you get a better understanding of what’s going on.
Have fun!
Do you need to hire top developers? Talk to Andela to help you scale.
Are you looking to accelerate your career as a developer? Andela is currently hiring senior developers. Apply now.
