Page 2 of 2
www.AssignmentPoint.com
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.