NationMaster - Encyclopedia: Binary search algorithm

A binary search algorithm (or binary chop) is a technique for finding a particular value in a sorted list. It makes progressively better guesses, and closes in on the sought value by selecting the median element in a list, comparing its value to the target value, and determining if the selected value is greater than, less than, or equal to the target value. A guess that turns out to be too high becomes the new top of the list, and a guess that is too low becomes the new bottom of the list. Pursuing this strategy iteratively, it narrows the search by a factor of two each time, and finds the target value. A binary search is an example of a dichotomic divide and conquer search algorithm. Alphabetical redirects here. ... This article is about the statistical concept. ... In computer science, a dichotomic search is a search algorithm that operates by selecting between two distinct alternatives (dichotomies) at each step. ... In computer science, divide and conquer (D&C) is an important algorithm design paradigm. ... In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. ...

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 now guess 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. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ...

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 organizing 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. In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value. ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ...

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. Interpolation search parallels how humans search through a telephone book. ...

The most straightforward implementation is recursive, which recursively searches the subrange dictated by the comparison:

It is invoked with initial low and high values of 0 and N-1. We can eliminate the tail recursion above and convert this to an iterative implementation: In computer science, tail recursion (or tail-end recursion) is a special case of recursion in which the last operation of the function is a recursive call. ...

Some implementations may not include the early termination branch, preferring to check at the end if the value was found, shown below. Checking to see if the value was found during the search (as opposed to at the end of the search) may seem a good idea, but there are extra computations involved in each iteration of the search. Also, with an array of length N using the low and high indices, the probability of actually finding the value on the first iteration is 1 / N, and the probability of finding it later on (before the end) is the about 1 / (high - low). The following checks for the value at the end of the search:

This algorithm has two other advantages. At the end of the loop, low points to the first entry greater than or equal to value, so a new entry can be inserted if no match is found. Moreover, it only requires one comparison; which could be significant for complex keys in languages which do not allow the result of a comparison to be saved.

In practice, one frequently uses a three-way comparison instead of two comparisons per loop. Also, real implementations using fixed-width integers with modular arithmetic need to account for the possibility of overflow. One frequently-used technique for this is to compute mid, so that two smaller numbers are ultimately added: In computer science, a three-way comparison takes two values A and B belonging to a type with a total order and determines whether A < B, A = B, or A > B in a single operation, in accordance with the mathematical law of trichotomy. ...

Equal elements

The elements of the list are not necessarily all unique. If one searches for a value that occurs multiple times in the list, the index returned will be of the first-encountered equal element, 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 positions of the values. Modifying the list even in seemingly unrelated ways such as adding elements elsewhere in the list may change the result.

To find all equal elements an upward and downward linear search can be carried out from the initial result, stopping each search when the element is no longer equal. Thus, e.g. in a table of cities sorted by country, we can find all cities in a given country.

Sort key

A list of pairs (p,q) can be sorted based on just p. Then the comparisons in the algorithm need only consider the values of p, not those of q. For example, in a table of cities sorted on a column "country" we can find cities in Germany by comparing country names with "Germany", instead of comparing whole rows. Such partial content is called a sort key.

Correctness and testing

Binary search is one of the trickiest "simple" algorithms to program correctly. When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding 90 percent failed to code a binary search correctly after several hours of working on it^[1], and another study shows that accurate code for it is only found in five out of twenty textbooks. (Kruse, 1999) Given this insight, it is important to remember that the best way to verify the correctness of a binary search algorithm is to thoroughly test it on a computer. It is difficult to visually analyze the code without making a mistake.

To that end, the following code will thoroughly test a binary search at every index for many multiple lengths of arrays:

 int offset, value, index, length; bool passed=true; for(offset=1; offset<5; offset++){ //tests with an offset between 1 and 4 for various amounts. for(length = 1; length < 2049; length++){ //make array longer on each iteration int A[length]; for(int i = 0; i < length; i++) //init array values from 0 to length-1 A[i] = i*offset; // check negative hits----------------------------------------------------- value = A[0] - 1; //searched value too low index = binarySearch(A, value); //binary search in array A if (!(index<0)) //error: found passed=false; //if this line executes, BUG in binary search value = A[length - 1] + 1; //searched value too high index = binarySearch(A, value); if (!(index<0)) //error: found passed=false; //if this line executes, BUG in binary search // check positive hits----------------------------------------------------- for(int i = 0; i < length; i++) { //search for every array value value = A[i]; index = binarySearch(A, value); if (!(index==i)) //error: array value NOT found passed=false; //if this line executes, BUG in binary search } } }

In the above C++ test-code, if passed is ever false, then the binary search function has a bug. Note that this code assumes that you are returning index of search value with array; in addition it does not handle properly duplicate values within your array, or errors that could be caused by more randomly distributed values. As such this should not be considered a complete proof of correctness, merely an aid for testing.

Performance

Binary search is a logarithmic algorithm and executes in O(

log N

) time. Specifically,

1 + log 2 N

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 some C-based languages tail recursion is not eliminated and the recursive version requires more stack space. In mathematics, if two variables of bn = x are known, the third can be found. ... For other uses, see Big O. In computational complexity theory, big O notation is often used to describe how the size of the input data affects an algorithms usage of computational resources (usually running time or memory). ... In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value. ... This article is about the concept of recursion. ... The word iteration is sometimes used in everyday English with a meaning virtually identical to repetition. ...

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 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 or even more in recent computers. The exact value depends entirely on the machine running the algorithm. For other uses, see cache (disambiguation). ...

When multiple binary searches are to be performed with the same key in related lists, fractional cascading can be used to speed up successive searches after the first one.

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.

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 $lceillog_2 Nrceil$ 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 $2lceil 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:

As one simple example, 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. Revision control (also known as version control (system) (VCS), source control or (source) code management (SCM)) is the management of multiple revisions of the same unit of information. ...

There are many occasions unrelated to computers when a binary search 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. (For finding non-deterministic bugs, where the test used will not always reveal the bug even if it is present in the revision, see Variations below.) See: Shotgun debugging. Shotgun debugging is a process of making relatively undirected changes to software in the hope that a bug will be perturbed out of existence. ...

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. In telephony, a telephone directory is a listing of telephone subscribers in a geographical area or subscribers to services provided by the organisation that publishes the directory. ...

Language support

Many standard libraries provide a way to do binary search. C provides bsearch(3) in its standard library. C++'s STL provides algorithm functions binary_search, 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. COBOL can perform binary search on internal tables using the SEARCH ALL statement. C is a general-purpose, block structured, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ... C++ (pronounced see plus plus, IPA: ) is a general-purpose programming language with high-level and low-level capabilities. ... [[Im[[Image:Example. ... In computer science, a subroutine (function, procedure, or subprogram) is a sequence of code which performs a specific task, as part of a larger program, and is grouped as one, or more, statement blocks; such code is sometimes collected into software libraries. ... Java refers to a number of computer software products and specifications from Sun Microsystems that together provide a system for developing application software and deploying it in a cross-platform environment. ... Microsoft Corporation, (NASDAQ: MSFT, HKSE: 4338) is a multinational computer technology corporation with global annual revenue of US$44. ... The . ... Generic programming is a style of computer programming where algorithms are written in an extended grammar and are made adaptable by specifying variable parts that are then somehow instantiated later by the compiler with respect to the base grammar. ... Python is a high-level programming language first released by Guido van Rossum in 1991. ... COBOL (pronounced //) is a Third-generation programming language, and one of the oldest programming languages still in active use. ...

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 $2lceillog_2krceil$ 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 log2 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. As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e. ... In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. ... In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...

For example, suppose we could answer "Does this n x n matrix have determinant larger than k?" in O(n²) time. Then, by using binary search, we could find the (ceiling of the) determinant itself in O(n²log d) time, where d is the determinant; notice that d is not the size of the input, but the size of the output. In algebra, a determinant is a function depending on n that associates a scalar, det(A), to every nÃ—n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ...

Variations

Several algorithms closely related to or extending binary search exist. For instance, noisy binary search solves the same class of projects as regular binary search, with the added complexity that any given test can return a false value at random. (Usually, the number of such erroneous results are bounded in some way, either in the form of an average error rate, or in the total number of errors allowed per element in the search space.) Optimal algorithms for several classes of noisy binary search problems have been known since the late seventies, and more recently, optimal algorithms for noisy binary search in quantum computers (where several elements can be tested at the same time) have been discovered.

Contents