The,Binary,Search,Algorithm,Bi computer The Binary Search Algorithm
----------------------------------------------------------Permission is granted for the below article to forward,reprint, distribute, use for ezine, newsletter, website,offer as free bonus or part of a product for sale as longas no changes a Gone are those times when the companies and the organisations didn't need a hi-tech system to handle them. Owing to the considerable increase in the business sector and thus, an enormous increase in the complexity of the organisational struc
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 Im 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 binary search 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 youll 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, lets say my response was Higher. What would you guess after? 75. Since its in between 50 100. If you didnt guess correctly, youll be facing the similar scenario as before. Youll 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.
The,Binary,Search,Algorithm,Bi