Binary Search

My blog is now located at http://www.WhoIsSethLong.com

A binary search is used to find if a value exists or what it’s position is in a sorted list.  You may have noticed that I put “sorted” in italics.  That’s because in order for the binary search to work, it must have a sorted list.

To better explain how the binary search works, lets walk through a simple example.  We will start off with a sorted list of numbers.

3, 5, 6, 9, 11, 12, 14

Next, we’ll need a number to search for.  For this example we’ll choose the number 12.

The binary search starts by selecting the middle position of the array and getting it’s value.  In our example we selected 9.

3, 5, 6, 9, 11, 12, 14

The algorithm then must decide if the number we are searching for is higher or lower then 9.  Since we are searching for 12, the number is higher then 9.  We must search to the right of 9 since we know that if there is a 12 in the list it must be to the right of 9.  We have now reduced the number of items to compare to in half with just 1 comparison! Pretty cool!  This leaves us with the follow numbers to search through.

11, 12, 14

We again select the middle position and compare it to the number we are searching for.  In this case the middle position returns a 12 which happens to be the number we are searching for.  Using the binary search we found our number in an array of 7 items using only 2 comparisons!

The key things to remember about a binary search are that it must have a sort list and it reduces the number of items it has to search through every time it does a comparison.

Coding a Binary Search

Coding a binary search is fairly straight forward.  We take the middle position of the array and compare it to our number.  If our number is higher then the middle position we then use the top half of the list.  If our number is lower we use the lower half of the list.  We then repeat the process till we find the number or run out of numbers to compare.

Here’s an example of a binary search using C#.

public int binarySearch(int[] array, int lower, int upper, int target)
{

    // set -1 to the location in case we don't find it
    int location = -1;    // keep looping till we run out of positions or we find it

    while (lower  array[mid])  // the mid position is less then our target
        {
            lower = mid + 1;
        }
        else  // the mid position is greater then our target
        {
            upper = mid - 1;
        }
    }

return location;

}

One thing you may have noticed is that you could have written the algorithm using recursion instead of using an iterative approach. So, here is another example of the same algorithm using a recursive method rather then an iterative one.

public int binarySearch(int[] array, int lower, int upper, int target)
{
    // get the mid position
    int mid = (lower + upper) / 2;    // does not exist

    if (lower >= upper)
    {
        return -1;
    }

    if (array[mid] == target) // mid position equals the target
    {
        return mid;
    }
    else if (target < array[mid]) // target is less then mid
    {
        return binarySearch(array, lower, mid - 1, target);
    }
    else // target is greater then mid
    {
        return binarySearch(array, mid + 1, upper, target);
    }
}

Performance

One of the greatest things about a binary search is the speed at which it can search through large lists.  For example, if we had a list with 1,000,000 items in it, a binary search could find the item we are searching for in under 20 comparisons!  Of course there is one drawback to the binary search, the list must be sorted.

Since every comparison the binary search performs cuts the number of items we have to search through in half, the binary search runs in logarithmic time or O(logN).

Well, that’s all for now.

- Seth Long