Intro to Binary Search Algorithm

Let’s say there is an unsorted array and you need to find certain values.
How would you search for those values?
You can’t avoid iterating the entire array every time you are searching since the array is unsorted.
Wouldn’t this be a very inefficient way of searching?
It may be fine if the size of the array is pretty small. However, what if there are one million elements in the array?
You probably do not want to iterate one million elements every time you search because it’s a waste of time.

Binary search algorithm is a very efficient search algorithm.
It requires the array to be sorted which may cost in the beginning.
However, once the array is sorted it’s extremely fast and easy to find an element in the array.
Let’s take a look at how binary search work in this post.

How does binary search work?

First of all, please note that an array needs to be sorted in order to apply binary search and you will see why as you read.
Basically binary search means you eliminate half of the search candidates every time you compare so you don’t have to check every element in the array.
I believe an example will explain the concept better than any other word.

Let’s say there is a sorted array with 12 elements.
And you would like to find the index of the element 81 if it exists.

Binary Search Algorithm Steps

The followings are steps of binary search algorithm.

1. Find a middle point and check if this element is equivalent as the search key 81
2. If yes, we found the element and return the index
3. If the key is smaller than the middle then we only need to search the left side of the middle point since the key will never exist on the right side.
4. If the key is greater than the middle then we only need to search the right side of the middle point since the key will never exist on the left side.
5. Iterate steps #1 – 4 until the element is found.

Although it is pretty simple it might not be clear to understand at first glance.

Binary Search Example

Let’s take a look at how we can find 81 from the above array.
First, we need to check the middle point which is located at index 5 with the value 25.

81 is not the same as 25.
Since 81 is greater than 25 we don’t need to search the left side of 25 which is from index 0 to index 4.
We throw away the left side and need to search the right side only.
What is the index range we need to search this time? It is from the index 6 to 11.

The middle element this time is located at index 8 with value 51.
But 51 is still not the same as 81.
Since 81 is still greater than 51 we can throw away the left side of the middle point (index 8).
81 simply can’t be found in the left side of the index 8.
What is the next index range we need to search for? It is from the index 9 to 11.

The middle element this time is located at index 10 with value 81.
We finally found the element at index 10!
How many times did we need to compare to find the element? Only 3 times.
It is indeed a very efficient algorithm to search!

Now you might ask what happens if the array doesn’t have an element we are looking for.
In that case, the middle point index will eventually go out of a valid index search range and binary search will return proper error code.
It will be clear once you see the code example below.

Code Example

#include <vector>
using namespace std;

/**
 * @brief  This function searches an element 'key' in the array using
 *         binary search algorithm
 * 
 * @param  array  array to search
 * @param  low    lower boundary index
 * @param  high   upper boundary index
 * @parma  key    key to search in the array
 * 
 * @return index of the found element, -1 if key doesn't exist
 */
int binarySearch(const vector<int> &array, int low, int high, int key)
{
    // weren't able to find element up to this point
    if (low > high)
    {
        return -1;
    }
    
    int middle = (low + high) / 2;
    if (array[middle] == key)
    {
        return middle;
    }
    else if (array[middle] > key)
    {
        // throw away right half of the array in searching
        return binarySearch(array, low, middle - 1, key);
    }
    else
    {
        // throw away left half of the array in searching
        return binarySearch(array, middle + 1, high, key);
    }
}

Performance

The search performance of binary search is O(log n) since it reduces half every time it compares.

Conclusion

Binary search is a great algorithm to find an element.
However, please note that it works great when applied to data structures such as array because you can easily throw away half of the search candidates.
You can still use binary search in linked list but it will not be as efficient as array.