Binary search

Fractional cascading efficiently solves a number of search problems in computational geometry and in numerous other fields.

If the target value is greater than the element, the search continues in the upper half of the array.

notation denotes the floor function that yields the greatest integer less than or equal to the argument, and

By doing so, an unsuccessful search can be represented as a path to an external node, whose parent is the single element that remains during the last iteration.

[14] This problem can similarly be reduced to determining the minimum external path length of all binary trees with

A variation of the algorithm checks whether the middle element is equal to the target at the end of the search.

[20] Sorted arrays with binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval, taking

[22] In addition, there are some operations, like finding the smallest and largest element, that can be performed efficiently on a sorted array.

[f][34] However, hashing is not useful for approximate matches, such as computing the next-smallest, next-largest, and nearest key, as the only information given on a failed search is that the target is not present in any record.

Some operations, like finding the smallest and largest element, can be done efficiently on sorted arrays but not on hash tables.

Some structures, such as Judy arrays, use a combination of approaches to mitigate this while retaining efficiency and the ability to perform approximate matching.

[40] To reduce the search space, the algorithm either adds or subtracts this change from the index of the middle element.

Uniform binary search may be faster on systems where it is inefficient to calculate the midpoint, such as on decimal computers.

Its time complexity grows more slowly than binary search, but this only compensates for the extra computation for large arrays.

[43] Fractional cascading is a technique that speeds up binary searches for the same element in multiple sorted arrays.

[46][47] Fractional cascading was originally developed to efficiently solve various computational geometry problems.

[46] Binary search has been generalized to work on certain types of graphs, where the target value is stored in a vertex instead of an array element.

Similarly, binary search trees are the case where the edges to the left or right subtrees are given when the queried vertex is unequal to the target.

[49][50][51] The noisy binary search problem can be considered as a case of the Rényi-Ulam game,[52] a variant of Twenty Questions where the answers may be wrong.

queries (representing iterations of the classical procedure), but the constant factor is less than one, providing for a lower time complexity on quantum computers.

The tablet contained about 500 sexagesimal numbers and their reciprocals sorted in lexicographical order, which made searching for a specific entry easier.

In addition, several lists of names that were sorted by their first letter were discovered on the Aegean Islands.

Catholicon, a Latin dictionary finished in 1286 CE, was the first work to describe rules for sorting words into alphabetical order, as opposed to just the first few letters.

[9] In 1946, John Mauchly made the first mention of binary search as part of the Moore School Lectures, a seminal and foundational college course in computing.

[9] In 1986, Bernard Chazelle and Leonidas J. Guibas introduced fractional cascading as a method to solve numerous search problems in computational geometry.

[46][60][61] Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly trickyWhen Jon Bentley assigned binary search as a problem in a course for professional programmers, he found that ninety percent failed to provide a correct solution after several hours of working on it, mainly because the incorrect implementations failed to run or returned a wrong answer in rare edge cases.

[63] Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years.

The Java programming language library implementation of binary search had the same overflow bug for more than nine years.

[64] In a practical implementation, the variables used to represent the indices will often be of fixed size (integers), and this can result in an arithmetic overflow for very large arrays.

Bentley found that most of the programmers who incorrectly implemented binary search made an error in defining the exit conditions.

binary-search
Binary search can be adapted to compute approximate matches. In the example above, the rank, predecessor, successor, and nearest neighbor are shown for the target value , which is not in the array.
A tree representing binary search. The array being searched here is , and the target value is .
The worst case is reached when the search reaches the deepest level of the tree, while the best case is reached when the target value is the middle element.
Binary search trees are searched using an algorithm similar to binary search.
Uniform binary search stores the difference between the current and the two next possible middle elements instead of specific bounds.
Visualization of exponential searching finding the upper bound for the subsequent binary search
Visualization of interpolation search using linear interpolation. In this case, no searching is needed because the estimate of the target's location within the array is correct. Other implementations may specify another function for estimating the target's location.
In fractional cascading , each array has pointers to every second element of another array, so only one binary search has to be performed to search all the arrays.
In noisy binary search, there is a certain probability that a comparison is incorrect.