The Binary Search Algorithm

The principle of a binary search can be generalized to any type of problem provided the elements of the search can form a sorted list or sequence and it is possible to make a comparison on the order in the sequence.

Playing the number game: Say we have a number range from 0 to 100, and now you have to pick the number I'm thinking of and depending on your guess ill answer with either "correct", "higher" or "lower". What number would you choose? The binary search provides the quickest solution to this problem; the number you should choose is 50.

The algorithm is one of the most efficient methods for locating the position of an element in a sorted list. The way it functions is by going straight to the middle of the list and checking whether the value is greater than, less than or equal to the element it's looking for. If equal to, then the element has been found, if not, then the algorithm eliminates half the list from consideration, and repeats the procedure on the remaining half. Thus, the number of elements needing to be checked is halved each time.

So, back to the number game: Why was "50" the best guess? Well in the best case your guess is correct, I was thinking of the number 50. In the worst case you'll either get a "Higher" or "Lower". Now think about the following, if you got "Higher" you eliminated numbers 0-49, or if you got "Lower" you eliminated 51-100, in other words, either way you eliminate HALF the possibilities. Now, let's say my response was "Higher". What would you guess after? 75. Since it's in between 50 - 100. If you didn't guess correctly, you'll be facing the similar scenario as before. You'll end up eliminating half the possibilities and eventually guessing correctly (assuming of course the number I was thinking of is within the bounds 0-100)

In computer programming terms, the algorithm operates on an ordered list of values and uses the order to conduct the search. So, for a list or array containing a large amount of elements the binary search will, on average, out-perform a linear search - in a list of one million items, a linear search will take an average of 500,000 comparisons to find a particular item. A binary search will take a maximum of 20. Pretty impressive huh. Beware though, as the search only works on a sorted list, if the list requires sorting first and only has a few elements then it may be faster to perform a linear search than to sort the list and then perform a binary search.

Implementing the algorithm in code is possible through recursion and it can also be implemented iteratively.

About The Author:

Elliott Nash is a .Net developer based in the beautiful Gold Coast, Australia. He is the author of the .Net Development Blog where you can read more on the binary search and how to implement it.

Article Source: http://EzineArticles.com/?expert=Elliott_Nash