Binary search algorithm

From Wikipedia, the free encyclopedia

You have new messages (last change).

A binary search algorithm (or binary chop) is a technique for finding a particular value in a linear array, by ruling out half of the data at each step, widely but not exclusively used in computer science. A binary search finds the median, makes a comparison to determine whether the desired value comes before or after it, and then searches the remaining half in the same manner. A binary search is an example of a divide and conquer algorithm (more specifically a decrease and conquer algorithm) and a dichotomic search (more at Search algorithm).

Contents

[edit] The algorithm

The most common application of binary search is to find a specific value in a sorted list. To cast this in the frame of the guessing game (see Example below), realize that we are now guessing the index, or numbered place, of the value in the list. This is useful because, given the index, other data structures will contain associated information. Suppose a data structure containing the classic collection of name, address, telephone number and so forth has been accumulated, and an array is prepared containing the names, numbered from one to N. A query might be: what is the telephone number for a given name X. To answer this the array would be searched and the index (if any) corresponding to that name determined, whereupon it would be used to report the associated telephone number and so forth. Appropriate provision must be made for the name not being in the list (typically by returning an index value of zero), indeed the question of interest might be only whether X is in the list or not.

If the list of names is in sorted order, a binary search will find a given name with far fewer probes than the simple procedure of probing each name in the list, one after the other in a Linear search, and the procedure is much simpler than organising a Hash table though that would be faster still, typically averaging just over one probe. This applies for a uniform distribution of search items but if it is known that some few items are much more likely to be sought for than the majority then a linear search with the list ordered so that the most popular items are first may do better.

The binary search begins by comparing the sought value X to the value in the middle of the list; because the values are sorted, it is clear whether the sought value would belong before or after that middle value, and the search then continues through the correct half in the same way. Only the sign of the difference is inspected: there is no attempt at an Interpolation search based on the size of the differences. Below is a C-pseudocode fragment which determines the index of a given value in a sorted list A between indices 1 and N (inclusive):

   BinarySearch( A, value ) {
       low = 0
       high = N - 1
       p = low+((high-low)/2)              //Initial probe position
       while ( low <= high) {
           if ( A[p] > value )
               high = p - 1
           else if ( A[p] < value )  //Wasteful second comparison forced by syntax limitations.
               low = p + 1
           else
               return p
           p = low+((high-low)/2)          //Next probe position.
       }
       return not_found
   }

Should the sorted array contain multiple elements with equal keys (for instance, {3,5,7,7,7,8,9}) then should such a key value be sought (for instance, 7), the index returned will be of the first-encountered equal element as the spans are halved, and this will not necessarily be that of the first, last, or middle element of the run of equal-key elements but will depend on the placement of the values with respect to N. That is, for a given list, the same index would be returned each time, but if the list is changed by adding deleting or moving elements, a different equal value may then be selected.

[edit] Performance

Binary search is a logarithmic algorithm and executes in O(log n) time. Specifically, 1 + log2N iterations are needed to return an answer. In most cases it is considerably faster than a linear search. It can be implemented using recursion or iteration, as shown above. In some languages it is more elegantly expressed recursively; however, in most C-based languages it is better to use a loop, because the stack use is increased with every recursion.

In most computer languages it is not possible to code a three-way choice based on the sign of a value, it is usually necessary to repeat the comparison at a price both in code size and execution time. The extra code will contribute to filling a processor's high-speed execution memory at no gain. The time wasted might be reduced slightly by ordering the branches so that earlier branches are the more likely ones to be taken: equality will only occur once. However, in performance-critical applications the effect on branch prediction should be evaluated.

Ruby is one exception where the '<=>' operator exists for such a 3-way comparison; in most languages the signum function exists which does a similar operation when the two 'needle' and 'haystack'-element can be subtracted: sgn(haystack[elem]-needle); in GNU Octave one can do sign(haystack(elem)-needle); to achieve the equivalent of a three-way branch. An older example is provided by fortran; refer to the discussion page.

Binary search can interact poorly with the memory hierarchy (i.e. caching), because of its random-access nature. For in-memory searching, if the interval to be searched is small, a linear search may have superior performance simply because it exhibits better locality of reference. For external searching, care must be taken or each of the first several probes will lead to a disk seek. A common technique for high performance applications is to abandon binary searching for linear searching as soon as the size of the remaining interval falls below a small value such as 8 or 16.

[edit] Examples

An example of binary search in action is a simple guessing game in which a player has to guess a positive integer, between 1 and N, selected by another player, using only questions answered with yes or no. Supposing N is 16 and the number 11 is selected, the game might proceed as follows.

  • Is the number greater than 8? (Yes).
  • Is the number greater than 12? (No)
  • Is the number greater than 10? (Yes)
  • Is the number greater than 11? (No)

Therefore, the number must be 11. At each step, we choose a number right in the middle of the range of possible values for the number. For example, once we know the number is greater than 8, but less than or equal to 12, we know to choose a number in the middle of the range [9, 12] (in this case 10 is optimal).

At most \lceil\log_2 N\rceil questions are required to determine the number, since each question halves the search space. Note that one less question (iteration) is required than for the general algorithm, since the number is constrained to a particular range.

Even if the number we're guessing can be arbitrarily large, in which case there is no upper bound N, we can still find the number in at most 2\lceil \log_2 k \rceil steps (where k is the (unknown) selected number) by first finding an upper bound by repeated doubling. For example, if the number were 11, we could use the following sequence of guesses to find it:

  • Is the number greater than 1? (Yes)
  • Is the number greater than 2? (Yes)
  • Is the number greater than 4? (Yes)
  • Is the number greater than 8? (Yes)
  • Is the number greater than 16? (No, N=16, proceed as above)

( We know the number is greater than 8 )

  • Is the number greater than 12? (No)
  • Is the number greater than 10? (Yes)
  • Is the number greater than 11? (No)

As one simple application, in revision control systems, it is possible to use a binary search to see in which revision a piece of content was added to a file. We simply do a binary search through the entire version history; if the content is not present in a particular version, it appeared later, while if it is present it appeared at that version or sooner. This is far quicker than checking every difference.

There are many occasions unrelated to computers when a binary chop is the quickest way to isolate a solution we seek. In troubleshooting a single problem with many possible causes, we can change half the suspects, see if the problem remains and deduce in which half the culprit is; change half the remaining suspects, and so on.

People typically use a mixture of the binary search and interpolative search algorithms when searching a telephone book, after the initial guess we exploit the fact that the entries are sorted and can rapidly find the required entry. For example when searching for Smith, if Rogers and Thomas have been found, one can flip to the page halfway between the previous guesses, if this shows Samson, we know that Smith is somewhere between the Samson and Thomas pages so we can bisect these.

[edit] Language support

Many standard libraries provide a way to do binary search. C provides bsearch in its standard library. C++'s STL provides algorithm functions lower bound and upper bound. Java offers a set of overloaded binarySearch() static methods in the classes Arrays and Collections for performing binary searches on Java arrays and Lists, respectively. They must be arrays of primitives, or the arrays or Lists must be of a type that implements the Comparable interface, or you must specify a custom Comparator object. Microsoft's .NET Framework 2.0 offers static generic versions of the Binary Search algorithm in its collection base classes. An example would be System.Array's method BinarySearch<T>(T[] array, T value). Python provides the bisect module.

[edit] Applications to complexity theory

Even if we do not know a fixed range the number k falls in, we can still determine its value by asking 2\lceil\log_2k\rceil simple yes/no questions of the form "Is k greater than x?" for some number x. As a simple consequence of this, if you can answer the question "Is this integer property k greater than a given value?" in some amount of time then you can find the value of that property in the same amount of time with an added factor of log k. This is called a reduction, and it is because of this kind of reduction that most complexity theorists concentrate on decision problems, algorithms that produce a simple yes/no answer.

For example, suppose we could answer "Does this n x n matrix have determinant larger than k?" in O(n2) time. Then, by using binary search, we could find the (ceiling of the) determinant itself in O(n2log d) time, where d is the determinant; notice that d is not the size of the input, but the size of the output.

[edit] See also

[edit] External links

[edit] References

  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.1: Searching an Ordered Table, pp.409–426.
Retrieved from "http://en.wikipedia.org../../../b/i/n/Binary_search_algorithm.html"