What is Binary Search Algorithm?

Binary search is one of those algorithms that you’ll come across on every (good) introductory computer science class. It’s an efficient algorithm for finding an item in an ordered list. For the sake of this example we’ll just assume this is an array. The goal of binary search is to be able to discard half of the array at every iteration, minimizing the number of elements we have to go through and leaving us with one final value.

Take for example the following array of integers:

int array[] = 
{ 
    1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 
};

Let’s say we are trying to find the index value of the number 7 in this array. There are 17 items in total, so the index values go from 0 to 16. Visually, it’s clear that the index value of 7 is 4, since it’s the fifth element in the array.

But what would be the best way for the computer to find the index value of the number we are looking for?
First, we store the min and max values, i.e. 0 and 16.

int min = 0;
int max = 16;

Now we have to come up with a guess. The smartest thing to do would be to guess an index value in the middle of the array. There are 17 items in this array, so the index values go from 0 to 16. The middle index value of this array would be 8, and that holds the number 14. This number is the first guess.

// This will round down if the quotient is not an integer
int guess = (min + max) / 2;

Our guess is now equal to 8, which is 14 in the array, since array[8] is equal to 14 .

If the number we were looking for was 14, we would be done! Since that is not the case, we will now discard half of the array (all the numbers after 14, i.e., index value 8, since we know that 14 is greater than 7, and our guess is too high).
After the first iteration, our search is now within: 1, 3, 4, 6, 7, 8, 10, 13
We don’t have to guess in the last half of the original array, because we know that all those values are too big. That’s why it’s important that we apply binary search to an ordered list.
Since our original guess of 14 was greater than 7, we now decrease it by 1 and store that into max:

max = guess - 1; // max is now equal to 7, which is 13 in the array

Now the search looks like this:

                      1, 3, 4, 6, 7, 8, 10, 13

min = 0
max = 7
guess = 3 

Because our guess was too low, we discard the bottom half of the array by increasing the min, conversely to what we previously did to max:

min = guess + 1; // min is now 4

By the next iteration, we are left with:

                             7, 8, 10, 13
min = 4
max = 7
guess = 5

Since index value 5 returns 8, we are now one over our target, so we repeat the process again, and we are left with:

                                  7
min = 4
max = 4
guess = 4

And we are left with only one value, 4, as the index of the target number we were looking for, which was 7.
The purpose of binary search is to get rid of half of the array at every iteration, so we only work on the values on which it makes sense to keep guessing.

The pseudo-code for this algorithm would look something like this:

• Let min = 0 , and let max = n (where n is the highest possible index value)
• Find the average of min and max , round down so it’s an integer. This is our guess
• If we guessed the number, stop, we got it!
• If guessis too low, set min equal to one more than guess
• If guessis too high, set max equal to one less than guess
• Go back to step two.