Binary search is a common algorithm taught in schools and while the idea is simple to understand, the real challenge is often implementing the algorithm. For those already familiar with the algorithm, feel free to scroll down to the implementation.
This article will aim to teach you how to remember binary search such that you will never have problems implementing it again.
Lets outline a few key ideas about binary search:
- Binary search can only be applied to sorted arrays/data structures AND sorted values
- Running time is O(log(n))
- Keep in mind the algorithm looks to answer when to look at the right half of values and left half of values (Think about answering “when to go ‘left’ and when to go ‘right’ ”)
From a collection of sorted values, define the low and high values of the boundaries.
Next find the middle point between those two values and process that value. With the information from the middle point decide whether to limit the scope of your answer to the remaining left half or the remaining right half of the values.
In the photo above, we process the middle point to learn that the answer must be in the left half of the array since the middle point is larger than the target we are looking for. Because the array is sorted, it is impossible for the answer to be in the right side of the array and can be immediately discarded. Set the upper boundary to be middle-1 and repeat the algorithm with the new boundaries.
The following code implements binary search to return the index of a desired value in a sorted array. Return -1 if the value does not exist in the array.
Let’s first look into our boundaries. Why did we set the boundaries as the following?
low = 0 high = nums.length-1