Understanding Binary Search and When to Use It
Do you remember the last time you pulled out a Yellow-pages or phonebook to look for a contact? It was so long ago, you probably don’t remember. Back in the 90s and earlier, when physical copies of the Yellow pages were still being delivered to your residence, you will go through pages to find a contact or an establishment. One way (also the slowest) is to go through it page by page from the beginning. This would be the linear solution and would be O(n) on the Big O Notation scale. If the name starts with the letter A, you might get lucky and find it within a second on the first page. What happens if it starts with a Z? There’s got to be a better way right?
BINARY SEARCH TO THE RESCUE! In computer science, binary search is also known as a half-interval search, logarithmic search, or the binary chop. It is a search algorithm that finds the position of a target value within a sorted array. The key take away here is that the array has be sorted. Luckily for us the phone book or our current contacts list is sorted. Using binary search, we can jump to the middle of the book and see if the name is on the page. If not, we can see if the name is to the left or the right of the page. By determining which side the name resides, we can eliminated the other half of the book. We repeat this step until we get to the exact name we are looking for.
Above is an example of a binary search function. Since this array is really short, we can easily see that the target’s index in the array is 1. This was done purposely to see if our function is able to get the exact same index. After running console.log(), we can confirm that the index of the target is one. If you try this with a target of 20, you will get an index of 9. If you try to target a number that doesn’t exist in the array, you will get the return value of -1. On the Big O Notation scale, binary search falls under O(log n), meaning it is a very efficient method for searching. Binary search is awesome, just remember to use it on a sorted array.
If you want a detailed explanation of binary search from a CS professor. You can check out this clip Below starting a 21:30:
