In this post, I’m going to explain the binary search algorithm, one of the most fundamental algorithms that you will need to learn.

Basic Intro

How does binary search work? Let’s say you want to search for the number 5 in a list of 10,000 numbers from 0 to 9,999. First, binary search discards the half of the list on the left—all the numbers that are less than 5. That gives us a new list of 5,000 numbers. We repeat this process until the resulting list contains only one number. That’s where—and only where—we can find the number we want. Well, that was quite something now let's expand on it a little more.

The Dictionary

Suppose that you are looking for the word Idempotent in a dictionary. If you follow a linear search algorithm then you will most likely search through each and every page looking for the numbers. Let's find out how to do it with binary search.

The Pseudocode

If you are following a binary search algorithm, then the course of action in pseudocode will be like this:

1. Open to the middle of the book.
   • Check if the word is there.
     • If it is there, return the index.
   • If not, check if the word is on the left or the right.
2. Again, open to the middle of the left or right side.
   • Check if the word is there.
     • If it is there, return the index.
   • If not, again split it in half again and repeat the steps from 2..

The Game

Let's play a game! You have to guess a number from 1 - 100 in minimum turns and I will tell you if it was high or low. Pretty simple right? Let's say how to would you go about it following binary search.

• You may first say 50 as we are looking at the middle.
  • I say that the number is lower.
• Then you may say 25, again splitting in between.
  • I again say that it is lower.
• Then you may say 13, as the middle value.
  • I say lower.
• Then you may say 7.
  • I again say lower.
• You say 4.
  • I repeat lower.
• You say 2.
  • I again say lower.
• Now, only one value is left. So, you finally say 1.

Of course, you could've got lucky and got the answer in between, say 7, was the number. But this brings the fact home that it only took me like 7 attempts to get to my number. If I had gone through a linear search, it could've taken me like 100 steps in the worst case.

O(?)

So, what is the complexity of this algorithm in Big O Notation? Quite simply, it took me log of 100 steps to solve the problem. Therefore, the complexity of Binary Search is O(log n). If you don't know why or how. I recommend you read my post on the Big O Notation.

Wrapping up.

This was a fairly basic post, that looks over one of the basic algorithms in Computer Science. Hope you learnt something! See you later!