Learn the Binary Search Algorithm

What is Binary Search?

Binary search is an efficient search algorithm on a sorted array of elements. The binary search algorithm comes from a family of algorithms called divide and conquer. You probably already use the binary search algorithm in your life.

Binary Search in the Real World

Let's say you're looking up a word "octothorpe" in the dictionary. How do you do it?

You know the words in the dictionary are sorted, so you probably open up the dictionary to somewhere in the middle.

You see words on the page you opened up begin with the letter "G". Octothorpe cannot possibly be on any page earlier than the page with the "G" words. So you completely disregard the pages earlier than the one with the "G" words.

What do you do next? You repeat the process on the remaining pages after the page with the "G" words. You keep repeating this process until you have found the page with "octothorpe".

This is exactly how binary search works. Binary search looks in the middle of a sorted array of elements. If the search term you're looking for is greater than the value in the middle, then you can disregard all the previous elements.

This is what makes binary search so efficient. At every step of binary search, you are eliminating half of the remaining elements. Eventually, the search space will be a single element, and the algorithm will terminate.

Check out this explanation from Harvard's CS50 course.