In computer science, binary search or binary chop is a search algorithm for finding a particular value in a linear array, by "ruling out" half of the data at each step. A binary search finds the median, makes a boolean comparison, the results of which will choose either the upper or lower quartile for further comparison, and so on into absolution. A binary search is an example of a divide and conquer algorithm and a dichotomic search. Wikibooks Wikiversity has more about this subject: School of Computer Science Open Directory Project: Computer Science Downloadable Science and Computer Science books Collection of Computer Science Bibliographies Belief that title science in computer science is inappropriate Categories: ‪Wikipedia articles needing priority cleanup‬ | ‪Computer science‬ ... 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. ... In computer science, divide and conquer (D&C) is an important algorithm design paradigm. ... In computer science, a dichotomic search is a search algorithm that operates by selecting between two distinct alternatives (dichotomies) at each step. ...

Examples

An example of binary search in action is a simple guessing game in which a player has to guess a positive integer selected by another player between 1 and N, 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] (either 10 or 11 will do).

At most 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 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)
• 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)

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. Revision control (also known as version control) is the management of multiple revisions of the same unit of information. ...

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 above, realize that we are now guessing the index, or numbered place, of the value in the list.

The search begins by examining the value in the center of the list; because the values are sorted, it then knows whether the value occurs before or after the center value, and searches through the correct half in the same way. Here is simple pseudocode which determines the index of a given value in a sorted list a between indices left and right:

 function binarySearch(a, value, left, right) if right < left return not found mid := floor((left+right)/2) if a[mid] = value return mid if value < a[mid] binarySearch(a, value, left, mid-1) else binarySearch(a, value, mid+1, right) 

Because the calls are tail-recursive, this can be rewritten as a loop, making the algorithm in-place: In computer science, tail recursion is a special case of recursion that can be transformed into an iteration. ... In computer science, an in-place algorithm is an algorithm which transforms a data structure using a small, constant amount of extra storage space. ...

 function binarySearch(a, value, left, right) while left ≤ right mid := floor((left+right)/2) if a[mid] = value return mid if value < a[mid] right := mid-1 else left := mid+1 return not found 

In both cases, the algorithm terminates because on each recursive call or iteration, the range of indexes right minus left always gets smaller, and so must eventually become negative.

Binary search is a logarithmic algorithm and executes in O(log n) time. Specifically, 1 + log₂N iterations are needed to return an answer. It is considerably faster than a linear search. It can be implemented using recursion or iteration, as shown above, although in many languages it is more elegantly expressed recursively. In mathematics, if two variables of bn = x are known, the third can be found. ... Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ... 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 mathematics and computer science, recursion specifies (or constructs) a class of objects (or an object from a certain class) by defining a few very simple base cases (often just one), and then defining rules to break down complex cases into simpler cases. ... Iteration is the repetition of a process, typically within a computer program. ...

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 binarySearch() method for the class java.util.Arrays. The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a standardized imperative computer programming language developed in the early 1970s by Dennis Ritchie for use on the Unix operating system. ... C++ (pronounced see plus plus, IPA: /siː plÉ™s plÉ™s/) is a general-purpose computer programming language. ... The Standard Template Library (STL) is a software library. ... 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. ... In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ... In mathematics, especially in order theory, an upper bound of a subset S of some partially ordered set is an element which is greater than or equal to every element of S. The term lower bound is defined dually. ... Java is an object-oriented programming language developed initially by James Gosling and colleagues at Sun Microsystems. ...

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 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. In computer science, computational complexity theory is the branch of the theory of computation that studies the resources required during computation to solve a given problem. ... In computability theory and computational complexity theory, a reduction is a transformation of one problem into another problem. ... In logic, a decision problem is determining whether or not there exists a decision procedure or algorithm for a class S of questions requiring a Boolean value (i. ...

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 linear 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. ...

External links

Wikisource has original text related to this article:

Binary search

• NIST Dictionary of Algorithms and Data Structures: binary search
• Tim Bray. On the Goodness of Binary Search. A short essay on the advantages of binary search and some Java sample code.
• Sparknotes: Binary search. Simplified overview of binary search.
• Mathworld: Binary search
• Binary Search Implementation in Visual Basic .NET (partially in English)

Wikipedia does not have an article with this exact name. ... Wikisource, The Free Library, is a Wikimedia project to build a free wiki library of primary source texts, along with translations of source-texts into any language and other supporting materials. ...

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.