 |
Business | Industries | Finance | Tax |
| Index: > A B C D E F G H I J K L M N O P Q R S T U V W X Y Z |
|
|||||
| First Prev [ 1 2 ] Next Last |
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.
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's no upper bound N, we can still find the number in at most steps 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 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. However, most useful revision control systems provide some easier to use function for this purpose such as CVS's annotate.
Binary search operates 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 indexes left and right:
binarySearch(a, value, left, right) if right < left return not found mid := floor((left+right)/2) if a[mid] = value return mid else if value < a[mid] binarySearch(a, value, left, mid-1) else if value > a[mid] binarySearch(a, value, mid+1, right)Because the calls are tail-recursive, this can be rewritten as a loop so that it requires only constant space:
binarySearch(a, value, left, right) while left <= right mid := floor((left+right)/2) if a[mid] = value return mid else if value < a[mid] right := mid-1 else if value > a[mid] left := mid+1 return not foundIn 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, 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.
Many standard libraries provide a way to do binary search. C++'s STL provides algorithm functions lower_bound and upper_boundIn 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. Formally, given a partially ordered set P. JavaJava is an object-oriented programming language developed primarily by James Gosling and colleagues at Sun Microsystems. The language, initially called Oak (named after the oak trees outside Gosling's office), was intended to replace C++, although the fea offers a binarySearch() method for the class Array.
| Politics | Business | Finance |
 |
 |
 |
|