Power of Binary Search

You have used Binary Search before!

Here is a question: when you last used a dictionary, how did you find the word you were looking for? Did you start from the beginning and read each and every word until you found the one you were looking for? Probably not.

This was the approach you used to navigate the dictionary: pick a random page. If your word is lexographically more than the first word on that page, you will pick a random page in the latter part of the dictionary. If your word was lexographically smaller, you will pick a page in the former half, depending on how close your word is. You keep on doing this till you find the word you are searching for.

You were using a form of binary search without even knowing it.

Understanding Binary Search

So let’s understand Binary Search. Let’s say your want to find an element in an array. Don’t be afraid of the arrays. Arrays are just lists data of a similar kind.

The array you are given is:

Let’s say you are asked to find position of 23 in this array. How will you find it?

Well one approach is to iterate through all the elements in the array and stop when you find the correct match. This approach is correct and will find the correct position of X. But, this is not a very fast way of finding that element because you are not utilizing one of the most useful properties of the array.

Take a moment to figure out the useful property that will help us to find X faster.

The useful property of the array is that the array is sorted. That is, the next element in the array is always greater than previous element. This will help us find the element much faster using Binary Search. Binary Search exploits the sorted nature of the array and finds an element much, much faster. Let’s see how.

Algorithm

1. We will find the middle element of the array. In the case, it is 16, since there are 4 elements to the left of it and 5 elements to the right of it. (Since it is an array of even number of elements)
2. We will compare 16 with X=23. Since X>16, we will look in the right half of the array.
3. Now our array trims down to 5 elements
4. We will repeat the same step again: find the middle element of the array. It is 56. As X(=23) is smaller than 56 we will look in the left half of this array.
5. Finally, our array only consists of 2 elements: 23 and 38. The middle element of this array will be 23. Comparing this to X(=23), we find that X=23. Hence we have found the element in the array.

The full algorithm can be visualized below, taken from here.

A shorter explanation for Tech readers

We basically ignore half of the elements just after one comparison.

1. Compare X with the middle element.
2. If X matches with the middle element, we return the mid index.
3. Else If X is greater than the mid element, then X can only lie in the right half sub-array after the mid element. So we recur for the right half.
4. Else (X is smaller) recur for the left half.

How did this save time?

If you haven’t figured out why this algorithm saves time, this is the reason: the algorithm throws out half of the current array after each comparison.

Let’s say that T(n) is the amount of time required for finding element in array of n elements. So the following recurrence relation will hold:

T(n) = T(n/2) + c

Since after one comparison it finds the element in an array of size n/2 and also requires a constant amount of time for a comparison. Solving this recurrence relation, we find that time complexity for this algorithm is O(log(N)). To demonstrate why this is faster than normal O(n), it’s because when N goes on increasing, O(N) increases significantly as compared to O(log(N)) as shown in the graph below.

Power of Binary Search

To give an idea of how fast binary search actually works, here is an example: In a database consisting of 100,000 users who are arranged alphabetically, you can find a particular user’s name in 10–15 comparisons! If a linear search algorithm was used in this case, it would have taken 100,000 comparisons in the worst case! I hope that demonstrates the power of binary search and why it’s so useful for us.

Binary search is regularly used by developers to improve performance of their app and to reduce time complexities

Code Implementation

• Following is a recursive implementation of the algorithm we discussed above.
• Following is a iterative implementation of the same.

// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;
        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }
    // We reach here when element is not
    // present in array
    return -1;
}
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "Element is not present in array"
                : cout << "Element is present at index " << result;
    return 0;
}
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
        // If the element is present at the middle
        // itself
        if (arr[mid] == x)
            return mid;
        // If element is smaller than mid, then
        // it can only be present in left subarray
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        // Else the element can only be present
        // in right subarray
        return binarySearch(arr, mid + 1, r, x);
    }
    // We reach here when element is not
    // present in array
    return -1;
}
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "Element is not present in array"
                : cout << "Element is present at index " << result;
    return 0;
}

Ending Remarks

• Always remember that Binary Search can only work on a sorted array.
• I hope you gained value from this post. If you did, be sure to follow me on Twitter.
• Till next time.