Algorithms: Binary Search

You are presented with a set of a 1000 numbers. You are tasked with finding the position of 73. The most obvious approach is to started with the first number and evaluate every number until 73 is found. This approach is called a linear search algorithm or sequential search algorithm. This works for a set of 1000 numbers, but consider if the set is increased to 10 million numbers. A linear search can not scale and is simply not suited for this many numbers, but a binary search algorithm can.

A binary search algorithm requires the data to be sorted. Once sorted, the value is found by finding the middle value and comparing it to the search value. If the search value is lower than the middle value, we take the first half of numbers and again we find the middle value and once again we compare it to the search value. If the search value is still lower, we again take the first half of numbers and find the middle value. And once again we compare the middle value to the search value. This process repeats itself until we find the search value or we run out of values.

Comparing the two algorithms for performance: A linear search of 10 million numbers, assuming 1 second per number, will consume roughly 116 days. A binary search of 10 million numbers, again assuming 1 second per number, will only consume about 23 seconds. When searching for numbers the binary search wins hands down.

Binary Search implemented in C#:

public int BinarySearch(int number, int[] collection)
{
    int low = 0;
    int high = collection.Length - 1; //collection[]; // find the last number, this assumes the collection is sorted.

    while (low <= high)
    {
        int mid = (low + high) / 2;

        if (collection[mid] < number)
        {
            low = mid + 1;
        }
        else if (collection[mid] > number)
        {
            high = mid - 1;
        }
        else 
        {
            return collection[mid];
        }
    }

    return -1;
}