Intro to Binary Search
Suppose you take a trip to a bookstore in search of a copy of Ada Lovelace’s autobiography. You get to the autobiography section of the shop and you can immediately tell the books have been organized alphabetically by last name. You go the middle of the section and hit the N’s knowing that if you look to your right at this point you will move past your book. You move left and again head to the middle of the your newly edited section. This process repeats, until finally you have the autobiography of the first computer programmer in your hands. This is binary search in real life action!
In computer science, binary search is a search algorithm that finds the index of a target value within a sorted array. Binary search compares the middle element of the array to the target. If they are not equal, the half in which the target cannot be found is discarded and the search continues on the remaining half, again comparing the middle value to the target. This process is repeated until the target is either found, or discovered to not be in the array at all.
So why is this a useful search tactic when putting together an algorithm? After all, you could just traverse through your data one element at a time and compare it to your target value. This simple approach, known as a linear search has a time complexity of O(n). But-if we know we are working with sorted data, we can do better!
This is where binary search comes into play! It allows us to find our target much faster with a time complexity of O(log n) as long as the data we are working with is sorted.
So how would you implement this into code? You can start by creating two variables to keep track of the start and end of the current subarray you’re searching. You’ll also want to keep track of the middle element so you can check to see if it’s greater, equal to, or less than your target element. If the middle element is equal to your target, you’ll simply return it. Otherwise you will update the start or end accordingly and continue looping. If the target is never found, you’ll return -1.
I hope you found this brief intro helpful, and that it gives you more insight into when and why you will want to implement binary search! Happy coding!
