Remembering Binary Search

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’ ”)

Algorithm

Problem statement: Find the index of a target value within an array of sorted values

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…