text:
Binary search

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.

Binary search runs in logarithmic time in the worst case, making $$O(\log n)$$ comparisons, where $$n$$ is the number of elements in the array. Binary search is faster than linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.

There are numerous variations of binary search. In particular, fractional cascading speeds up binary searches for the same value in multiple arrays. Fractional cascading efficiently solves a number of search problems in computational geometry and in numerous other fields. Exponential search extends binary search to unbounded lists. The binary search tree and B-tree data structures are based on binary search.

Algorithm
Binary search works on sorted arrays. Binary search begins by comparing an element in the middle of the array with the target value. If the target value matches the element, its position in the array is returned. If the target value is less than the element, the search continues in the lower half of the array. If the target value is greater than the element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration.

Procedure
Given an array $$A$$ of $$n$$ elements with values or records $$A_0,A_1,A_2,\ldots,A_{n-1}$$sorted such that $$A_0 \leq A_1 \leq A_2 \leq \cdots \leq A_{n-1}$$, and target value $$T$$, the following subroutine uses binary search to find the index of $$T$$ in $$A$$.
 * 1) Set $$L$$ to $$ 0$$ and $$R$$ to $$n-1$$.
 * 2) If $$L>R$$, the search terminates as unsuccessful.
 * 3) Set $$m$$ (the position of the middle element) to the floor of $$\frac{L+R}{2}$$, which is the greatest integer less than or equal to $$\frac{L+R}{2}$$.
 * 4) If $$A_m < T$$, set $$L$$ to $$m+1$$ and go to step 2.
 * 5) If $$A_m > T$$, set $$R$$ to $$m-1$$ and go to step 2.
 * 6) Now $$A_m = T$$, the search is done; return $$m$$.

This iterative procedure keeps track of the search boundaries with the two variables $$L$$ and $$R$$. The procedure may be expressed in pseudocode as follows, where the variable names and types remain the same as above,  is the floor function, and   refers to a specific value that conveys the failure of the search. function binary_search(A, n, T) is L := 0 R := n − 1 while L ≤ R do m := floor((L + R) / 2) if A[m] < T then L := m + 1 else if A[m] > T then R := m − 1 else: return m    return unsuccessful

Alternatively, the algorithm may take the ceiling of $$\frac{L+R}{2}$$. This may change the result if the target value appears more than once in the array.

Alternative procedure
In the above procedure, the algorithm checks whether the middle element ($$m$$) is equal to the target ($$T$$) in every iteration. Some implementations leave out this check during each iteration. The algorithm would perform this check only when one element is left (when $$L=R$$). This results in a faster comparison loop, as one comparison is eliminated per iteration, while it requires only one more iteration on average.

Hermann Bottenbruch published the first implementation to leave out this check in 1962.

 * 1) Set $$L$$ to $$ 0$$ and $$R$$ to $$n-1$$.
 * 2) While $$L \neq R$$,
 * 3) Set $$m$$ (the position of the middle element) to the ceiling of $$\frac{L+R}{2}$$, which is the least integer greater than or equal to $$\frac{L+R}{2}$$.
 * 4) If $$A_m > T$$, set $$R$$ to $$m-1$$.
 * 5) Else, $$A_m \leq T$$; set $$L$$ to $$m$$.
 * 6) Now $$L=R$$, the search is done. If $$A_L=T$$, return $$L$$. Otherwise, the search terminates as unsuccessful.

Where  is the ceiling function, the pseudocode for this version is:

function binary_search_alternative(A, n, T) is L := 0 R := n − 1 while L != R do m := ceil((L + R) / 2) if A[m] > T then R := m − 1 else: L := m    if A[L] = T then return L    return unsuccessful

Duplicate elements
The procedure may return any index whose element is equal to the target value, even if there are duplicate elements in the array. For example, if the array to be searched was $$[1,2,3,4,4,5,6,7]$$ and the target was $$4$$, then it would be correct for the algorithm to either return the 4th (index 3) or 5th (index 4) element. The regular procedure would return the 4th element (index 3) in this case. It does not always return the first duplicate (consider $$[1,2,4,4,4,5,6,7]$$ which still returns the 4th element). However, it is sometimes necessary to find the leftmost element or the rightmost element for a target value that is duplicated in the array. In the above example, the 4th element is the leftmost element of the value 4, while the 5th element is the rightmost element of the value 4. The alternative procedure above will always return the index of the rightmost element if such an element exists.

Procedure for finding the leftmost element
To find the leftmost element, the following procedure can be used:

 * 1) Set $$L$$ to $$ 0$$ and $$R$$ to $$n$$.
 * 2) While $$L < R$$,
 * 3) Set $$m$$ (the position of the middle element) to the floor of $$\frac{L+R}{2}$$, which is the greatest integer less than or equal to $$\frac{L+R}{2}$$.
 * 4) If $$A_m < T$$, set $$L$$ to $$m+1$$.
 * 5) Else, $$A_m \geq T$$; set $$R$$ to $$m$$.
 * 6) Return $$L$$.

If $$L < n$$ and $$A_L = T$$, then $$A_L$$ is the leftmost element that equals $$T$$. Even if $$T$$ is not in the array, $$L$$ is the rank of $$T$$ in the array, or the number of elements in the array that are less than $$T$$.

Where  is the floor function, the pseudocode for this version is:

function binary_search_leftmost(A, n, T): L := 0 R := n    while L < R:         m := floor((L + R) / 2) if A[m] < T:            L := m + 1 else: R := m    return L

Procedure for finding the rightmost element
To find the rightmost element, the following procedure can be used:

 * 1) Set $$L$$ to $$ 0$$ and $$R$$ to $$n$$.
 * 2) While $$L < R$$,
 * 3) Set $$m$$ (the position of the middle element) to the floor of $$\frac{L+R}{2}$$, which is the greatest integer less than or equal to $$\frac{L+R}{2}$$.
 * 4) If $$A_m > T$$, set $$R$$ to $$m$$.
 * 5) Else, $$A_m \leq T$$; set $$L$$ to $$m+1$$.
 * 6) Return $$R - 1$$.

If $$R > 0$$ and $$A_{R-1}=T$$, then $$A_{R-1}$$ is the rightmost element that equals $$T$$. Even if $$T$$ is not in the array, $$n-R$$ is the number of elements in the array that are greater than $$T$$.

Where  is the floor function, the pseudocode for this version is:

function binary_search_rightmost(A, n, T): L := 0 R := n    while L < R:         m := floor((L + R) / 2) if A[m] > T:            R := m         else: L := m + 1 return R - 1

Approximate matches
The above procedure only performs exact matches, finding the position of a target value. However, it is trivial to extend binary search to perform approximate matches because binary search operates on sorted arrays. For example, binary search can be used to compute, for a given value, its rank (the number of smaller elements), predecessor (next-smallest element), successor (next-largest element), and nearest neighbor. Range queries seeking the number of elements between two values can be performed with two rank queries.
 * Rank queries can be performed with the procedure for finding the leftmost element. The number of elements less than the target value is returned by the procedure.
 * Predecessor queries can be performed with rank queries. If the rank of the target value is $$r$$, its predecessor is $$r-1$$.
 * For successor queries, the procedure for finding the rightmost element can be used. If the result of running the procedure for the target value is $$r$$, then the successor of the target value is $$r+1$$.
 * The nearest neighbor of the target value is either its predecessor or successor, whichever is closer.
 * Range queries are also straightforward. Once the ranks of the two values are known, the number of elements greater than or equal to the first value and less than the second is the difference of the two ranks. This count can be adjusted up or down by one according to whether the endpoints of the range should be considered to be part of the range and whether the array contains entries matching those endpoints.

Performance

In terms of the number of comparisons, the performance of binary search can be analyzed by viewing the run of the procedure on a binary tree. The root node of the tree is the middle element of the array. The middle element of the lower half is the left child node of the root, and the middle element of the upper half is the right child node of the root. The rest of the tree is built in a similar fashion. Starting from the root node, the left or right subtrees are traversed depending on whether the target value is less or more than the node under consideration.

In the worst case, binary search makes $\lfloor \log_2 (n) + 1 \rfloor$ iterations of the comparison loop, where the $\lfloor\cdot \rfloor$  notation denotes the floor function that yields the greatest integer less than or equal to the argument, and $\log_2$  is the binary logarithm. This is because the worst case is reached when the search reaches the deepest level of the tree, and there are always $\lfloor \log_2 (n) + 1 \rfloor$ levels in the tree for any binary search.

The worst case may also be reached when the target element is not in the array. If $n$ is one less than a power of two, then this is always the case. Otherwise, the search may perform $\lfloor \log_2 (n) + 1 \rfloor$ iterations if the search reaches the deepest level of the tree. However, it may make $\lfloor \log_2 (n) \rfloor$ iterations, which is one less than the worst case, if the search ends at the second-deepest level of the tree.

On average, assuming that each element is equally likely to be searched, binary search makes $$\lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n$$ iterations when the target element is in the array. This is approximately equal to $$\log_2(n) - 1$$ iterations. When the target element is not in the array, binary search makes $$\lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1)$$ iterations on average, assuming that the range between and outside elements is equally likely to be searched.

In the best case, where the target value is the middle element of the array, its position is returned after one iteration.

In terms of iterations, no search algorithm that works only by comparing elements can exhibit better average and worst-case performance than binary search. The comparison tree representing binary search has the fewest levels possible as every level above the lowest level of the tree is filled completely. Otherwise, the search algorithm can eliminate few elements in an iteration, increasing the number of iterations required in the average and worst case. This is the case for other search algorithms based on comparisons, as while they may work faster on some target values, the average performance over all elements is worse than binary search. By dividing the array in half, binary search ensures that the size of both subarrays are as similar as possible.

Space complexity
Binary search requires three pointers to elements, which may be array indices or pointers to memory locations, regardless of the size of the array. Therefore, the space complexity of binary search is $$O(1)$$ in the word RAM model of computation.

Derivation of average case
The average number of iterations performed by binary search depends on the probability of each element being searched. The average case is different for successful searches and unsuccessful searches. It will be assumed that each element is equally likely to be searched for successful searches. For unsuccessful searches, it will be assumed that the intervals between and outside elements are equally likely to be searched. The average case for successful searches is the number of iterations required to search every element exactly once, divided by $$n$$, the number of elements. The average case for unsuccessful searches is the number of iterations required to search an element within every interval exactly once, divided by the $$n + 1$$ intervals.

Successful searches
In the binary tree representation, a successful search can be represented by a path from the root to the target node, called an internal path. The length of a path is the number of edges (connections between nodes) that the path passes through. The number of iterations performed by a search, given that the corresponding path has length $$l$$, is $$l + 1$$ counting the initial iteration. The internal path length is the sum of the lengths of all unique internal paths. Since there is only one path from the root to any single node, each internal path represents a search for a specific element. If there are $$n$$ elements, which is a positive integer, and the internal path length is $$I(n)$$, then the average number of iterations for a successful search $$T(n) = 1 + \frac{I(n)}{n}$$, with the one iteration added to count the initial iteration.

Since binary search is the optimal algorithm for searching with comparisons, this problem is reduced to calculating the minimum internal path length of all binary trees with $$n$$ nodes, which is equal to:

$$ I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor $$

For example, in a 7-element array, the root requires one iteration, the two elements below the root require two iterations, and the four elements below require three iterations. In this case, the internal path length is:

$$ \sum_{k=1}^7 \left \lfloor \log_2(k) \right \rfloor = 0 + 2(1) + 4(2) = 2 + 8 = 10 $$

The average number of iterations would be $$1 + \frac{10}{7} = 2 \frac{3}{7}$$ based on the equation for the average case. The sum for $$I(n)$$ can be simplified to:

$$ I(n) = \sum_{k=1}^n \left \lfloor \log_2(k) \right \rfloor = (n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2 $$

Substituting the equation for $$I(n)$$ into the equation for $$T(n)$$:

$$ T(n) = 1 + \frac{(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2}{n} = \lfloor \log_2 (n) \rfloor + 1 - (2^{\lfloor \log_2 (n) \rfloor + 1} - \lfloor \log_2 (n) \rfloor - 2)/n $$

For integer $$n$$, this is equivalent to the equation for the average case on a successful search specified above.

Unsuccessful searches
Unsuccessful searches can be represented by augmenting the tree with external nodes, which forms an extended binary tree. If an internal node, or a node present in the tree, has fewer than two child nodes, then additional child nodes, called external nodes, are added so that each internal node has two children. 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. An external path is a path from the root to an external node. The external path length is the sum of the lengths of all unique external paths. If there are $$n$$ elements, which is a positive integer, and the external path length is $$E(n)$$, then the average number of iterations for an unsuccessful search $$T'(n)=\frac{E(n)}{n+1}$$, with the one iteration added to count the initial iteration. The external path length is divided by $$n+1$$ instead of $$n$$ because there are $$n+1$$ external paths, representing the intervals between and outside the elements of the array.

This problem can similarly be reduced to determining the minimum external path length of all binary trees with $$n$$ nodes. For all binary trees, the external path length is equal to the internal path length plus $$2n$$. Substituting the equation for $$I(n)$$:

$$ E(n) = I(n) + 2n = \left[(n + 1)\left \lfloor \log_2(n + 1) \right \rfloor - 2^{\left \lfloor \log_2(n+1) \right \rfloor + 1} + 2\right] + 2n = (n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1} $$

Substituting the equation for $$E(n)$$ into the equation for $$T'(n)$$, the average case for unsuccessful searches can be determined:

$$ T'(n) = \frac{(n + 1) (\lfloor \log_2 (n) \rfloor + 2) - 2^{\lfloor \log_2 (n) \rfloor + 1}}{(n+1)} = \lfloor \log_2 (n) \rfloor + 2 - 2^{\lfloor \log_2 (n) \rfloor + 1}/(n + 1) $$

Performance of alternative procedure
Each iteration of the binary search procedure defined above makes one or two comparisons, checking if the middle element is equal to the target in each iteration. Assuming that each element is equally likely to be searched, each iteration makes 1.5 comparisons on average. A variation of the algorithm checks whether the middle element is equal to the target at the end of the search. On average, this eliminates half a comparison from each iteration. This slightly cuts the time taken per iteration on most computers. However, it guarantees that the search takes the maximum number of iterations, on average adding one iteration to the search. Because the comparison loop is performed only $\lfloor \log_2 (n) + 1 \rfloor$ times in the worst case, the slight increase in efficiency per iteration does not compensate for the extra iteration for all but very large $n$.

Running time and cache use
In analyzing the performance of binary search, another consideration is the time required to compare two elements. For integers and strings, the time required increases linearly as the encoding length (usually the number of bits) of the elements increase. For example, comparing a pair of 64-bit unsigned integers would require comparing up to double the bits as comparing a pair of 32-bit unsigned integers. The worst case is achieved when the integers are equal. This can be significant when the encoding lengths of the elements are large, such as with large integer types or long strings, which makes comparing elements expensive. Furthermore, comparing floating-point values (the most common digital representation of real numbers) is often more expensive than comparing integers or short strings.

On most computer architectures, the processor has a hardware cache separate from RAM. Since they are located within the processor itself, caches are much faster to access but usually store much less data than RAM. Therefore, most processors store memory locations that have been accessed recently, along with memory locations close to it. For example, when an array element is accessed, the element itself may be stored along with the elements that are stored close to it in RAM, making it faster to sequentially access array elements that are close in index to each other (locality of reference). On a sorted array, binary search can jump to distant memory locations if the array is large, unlike algorithms (such as linear search and linear probing in hash tables) which access elements in sequence. This adds slightly to the running time of binary search for large arrays on most systems.

Binary search versus other schemes
Sorted arrays with binary search are a very inefficient solution when insertion and deletion operations are interleaved with retrieval, taking $O(n)$ time for each such operation. In addition, sorted arrays can complicate memory use especially when elements are often inserted into the array. There are other data structures that support much more efficient insertion and deletion. Binary search can be used to perform exact matching and set membership (determining whether a target value is in a collection of values). There are data structures that support faster exact matching and set membership. However, unlike many other searching schemes, binary search can be used for efficient approximate matching, usually performing such matches in $O(\log n)$ time regardless of the type or structure of the values themselves. In addition, there are some operations, like finding the smallest and largest element, that can be performed efficiently on a sorted array.

Linear search
Linear search is a simple search algorithm that checks every record until it finds the target value. Linear search can be done on a linked list, which allows for faster insertion and deletion than an array. Binary search is faster than linear search for sorted arrays except if the array is short, although the array needs to be sorted beforehand. All sorting algorithms based on comparing elements, such as quicksort and merge sort, require at least $O(n \log n)$ comparisons in the worst case. Unlike linear search, binary search can be used for efficient approximate matching. There are operations such as finding the smallest and largest element that can be done efficiently on a sorted array but not on an unsorted array.

Trees

A binary search tree is a binary tree data structure that works based on the principle of binary search. The records of the tree are arranged in sorted order, and each record in the tree can be searched using an algorithm similar to binary search, taking on average logarithmic time. Insertion and deletion also require on average logarithmic time in binary search trees. This can be faster than the linear time insertion and deletion of sorted arrays, and binary trees retain the ability to perform all the operations possible on a sorted array, including range and approximate queries.

However, binary search is usually more efficient for searching as binary search trees will most likely be imperfectly balanced, resulting in slightly worse performance than binary search. This even applies to balanced binary search trees, binary search trees that balance their own nodes, because they rarely produce the tree with the fewest possible levels. Except for balanced binary search trees, the tree may be severely imbalanced with few internal nodes with two children, resulting in the average and worst-case search time approaching $n$ comparisons. Binary search trees take more space than sorted arrays.

Binary search trees lend themselves to fast searching in external memory stored in hard disks, as binary search trees can be efficiently structured in filesystems. The B-tree generalizes this method of tree organization. B-trees are frequently used to organize long-term storage such as databases and filesystems.

Hashing
For implementing associative arrays, hash tables, a data structure that maps keys to records using a hash function, are generally faster than binary search on a sorted array of records. Most hash table implementations require only amortized constant time on average. 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. Binary search is ideal for such matches, performing them in logarithmic time. Binary search also supports approximate matches. Some operations, like finding the smallest and largest element, can be done efficiently on sorted arrays but not on hash tables.

Set membership algorithms
A related problem to search is set membership. Any algorithm that does lookup, like binary search, can also be used for set membership. There are other algorithms that are more specifically suited for set membership. A bit array is the simplest, useful when the range of keys is limited. It compactly stores a collection of bits, with each bit representing a single key within the range of keys. Bit arrays are very fast, requiring only $O(1)$ time. The Judy1 type of Judy array handles 64-bit keys efficiently.

For approximate results, Bloom filters, another probabilistic data structure based on hashing, store a set of keys by encoding the keys using a bit array and multiple hash functions. Bloom filters are much more space-efficient than bit arrays in most cases and not much slower: with $k$ hash functions, membership queries require only $O(k)$  time. However, Bloom filters suffer from false positives.

Other data structures
There exist data structures that may improve on binary search in some cases for both searching and other operations available for sorted arrays. For example, searches, approximate matches, and the operations available to sorted arrays can be performed more efficiently than binary search on specialized data structures such as van Emde Boas trees, fusion trees, tries, and bit arrays. These specialized data structures are usually only faster because they take advantage of the properties of keys with a certain attribute (usually keys that are small integers), and thus will be time or space consuming for keys that lack that attribute. As long as the keys can be ordered, these operations can always be done at least efficiently on a sorted array regardless of the keys. Some structures, such as Judy arrays, use a combination of approaches to mitigate this while retaining efficiency and the ability to perform approximate matching.

Uniform binary search
Uniform binary search stores, instead of the lower and upper bounds, the difference in the index of the middle element from the current iteration to the next iteration. A lookup table containing the differences is computed beforehand. For example, if the array to be searched is $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]$, the middle element ($$m$$) would be $6$. In this case, the middle element of the left subarray ($[1, 2, 3, 4, 5]$) is $3$ and the middle element of the right subarray ($[7, 8, 9, 10, 11]$) is $9$. Uniform binary search would store the value of $3$ as both indices differ from $6$ by this same amount. 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.

Exponential search
Exponential search extends binary search to unbounded lists. It starts by finding the first element with an index that is both a power of two and greater than the target value. Afterwards, it sets that index as the upper bound, and switches to binary search. A search takes $\lfloor \log_2 x + 1\rfloor$ iterations before binary search is started and at most $\lfloor \log_2 x \rfloor$  iterations of the binary search, where $x$  is the position of the target value. Exponential search works on bounded lists, but becomes an improvement over binary search only if the target value lies near the beginning of the array.

Interpolation search
Instead of calculating the midpoint, interpolation search estimates the position of the target value, taking into account the lowest and highest elements in the array as well as length of the array. It works on the basis that the midpoint is not the best guess in many cases. For example, if the target value is close to the highest element in the array, it is likely to be located near the end of the array.

A common interpolation function is linear interpolation. If $$A$$ is the array, $$L, R$$ are the lower and upper bounds respectively, and $$T$$ is the target, then the target is estimated to be about $$(T - A_L) / (A_R - A_L)$$ of the way between $$L$$ and $$R$$. When linear interpolation is used, and the distribution of the array elements is uniform or near uniform, interpolation search makes $O(\log \log n)$ comparisons.

In practice, interpolation search is slower than binary search for small arrays, as interpolation search requires extra computation. Its time complexity grows more slowly than binary search, but this only compensates for the extra computation for large arrays.

Fractional cascading
Fractional cascading is a technique that speeds up binary searches for the same element in multiple sorted arrays. Searching each array separately requires $O(k \log n)$ time, where $k$  is the number of arrays. Fractional cascading reduces this to $O(k + \log n)$ by storing specific information in each array about each element and its position in the other arrays.

Fractional cascading was originally developed to efficiently solve various computational geometry problems. Fractional cascading has been applied elsewhere, such as in data mining and Internet Protocol routing.

Generalization to graphs
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. Binary search trees are one such generalization—when a vertex (node) in the tree is queried, the algorithm either learns that the vertex is the target, or otherwise which subtree the target would be located in. However, this can be further generalized as follows: given an undirected, positively weighted graph and a target vertex, the algorithm learns upon querying a vertex that it is equal to the target, or it is given an incident edge that is on the shortest path from the queried vertex to the target. The standard binary search algorithm is simply the case where the graph is a path. 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. For all undirected, positively weighted graphs, there is an algorithm that finds the target vertex in $$O(\log n)$$ queries in the worst case.

Noisy binary search
Noisy binary search algorithms solve the case where the algorithm cannot reliably compare elements of the array. For each pair of elements, there is a certain probability that the algorithm makes the wrong comparison. Noisy binary search can find the correct position of the target with a given probability that controls the reliability of the yielded position. Every noisy binary search procedure must make at least $$(1 - \tau)\frac{\log_2 (n)}{H(p)} - \frac{10}{H(p)}$$ comparisons on average, where $$H(p) = -p \log_2 (p) - (1 - p) \log_2 (1 - p)$$ is the binary entropy function and $$\tau$$ is the probability that the procedure yields the wrong position. The noisy binary search problem can be considered as a case of the Rényi-Ulam game, a variant of Twenty Questions where the answers may be wrong.

Quantum binary search
Classical computers are bounded to the worst case of exactly $\lfloor \log_2 n + 1 \rfloor$ iterations when performing binary search. Quantum algorithms for binary search are still bounded to a proportion of $\log_2 n$ queries (representing iterations of the classical procedure), but the constant factor is less than one, providing for a lower time complexity on quantum computers. Any exact quantum binary search procedure—that is, a procedure that always yields the correct result—requires at least $\frac{1}{\pi}(\ln n - 1) \approx 0.22 \log_2 n$ queries in the worst case, where $\ln$  is the natural logarithm. There is an exact quantum binary search procedure that runs in $4 \log_{605} n \approx 0.433 \log_2 n$ queries in the worst case. In comparison, Grover's algorithm is the optimal quantum algorithm for searching an unordered list of elements, and it requires $$O(\sqrt{n})$$ queries.

History
The idea of sorting a list of items to allow for faster searching dates back to antiquity. The earliest known example was the Inakibit-Anu tablet from Babylon dating back to c. 200 BCE. 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.

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. In 1957, William Wesley Peterson published the first method for interpolation search. Every published binary search algorithm worked only for arrays whose length is one less than a power of two until 1960, when Derrick Henry Lehmer published a binary search algorithm that worked on all arrays. In 1962, Hermann Bottenbruch presented an ALGOL 60 implementation of binary search that placed the comparison for equality at the end, increasing the average number of iterations by one, but reducing to one the number of comparisons per iteration. The uniform binary search was developed by A. K. Chandra of Stanford University in 1971. In 1986, Bernard Chazelle and Leonidas J. Guibas introduced fractional cascading as a method to solve numerous search problems in computational geometry.

Implementation issues
"Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky"

When 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. A study published in 1988 shows that accurate code for it is only found in five out of twenty textbooks. 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.

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. If the midpoint of the span is calculated as $$\frac{L+R}{2}$$, then the value of $$L+R$$ may exceed the range of integers of the data type used to store the midpoint, even if $$L$$ and $$R$$ are within the range. If $$L$$ and $$R$$ are nonnegative, this can be avoided by calculating the midpoint as $$L+\frac{R-L}{2}$$.

An infinite loop may occur if the exit conditions for the loop are not defined correctly. Once $$L$$ exceeds $$R$$, the search has failed and must convey the failure of the search. In addition, the loop must be exited when the target element is found, or in the case of an implementation where this check is moved to the end, checks for whether the search was successful or failed at the end must be in place. Bentley found that most of the programmers who incorrectly implemented binary search made an error in defining the exit conditions.

Library support
Many languages' standard libraries include binary search routines:

 * C provides the function  in its standard library, which is typically implemented via binary search, although the official standard does not require it so.
 * C++'s standard library provides the functions,  ,   and.
 * D's standard library Phobos, in  module provides a type   (returned by   and   functions) with methods ,  ,   and  , that use binary search techniques by default for ranges that offer random access.
 * COBOL provides the  verb for performing binary searches on COBOL ordered tables.
 * Go's  standard library package contains the functions ,  ,  , and  , which implement general binary search, as well as specific implementations for searching slices of integers, floating-point numbers, and strings, respectively.
 * Java offers a set of overloaded  static methods in the classes  and  in the standard   package for performing binary searches on Java arrays and on  s, respectively.
 * Microsoft's .NET Framework 2.0 offers static generic versions of the binary search algorithm in its collection base classes. An example would be 's method.
 * For Objective-C, the Cocoa framework provides the  method in Mac OS X 10.6+. Apple's Core Foundation C framework also contains a   function.
 * Python provides the  module that keeps a list in sorted order without having to sort the list after each insertion.
 * Ruby's Array class includes a  method with built-in approximate matching.
 * Rust's slice primitive provides,  ,  , and.

title: Binary search


text:
Belle and Sebastian

Belle and Sebastian are a Scottish indie pop band formed in Glasgow in 1996. Led by Stuart Murdoch, the band has released twelve studio albums. They are often compared with acts such as the Smiths and Nick Drake. The name "Belle and Sebastian" comes from the 1965 television series Belle and Sebastian. Though consistently lauded by critics, Belle and Sebastian's "wistful pop" has enjoyed only limited commercial success.

Formation, early years and Tigermilk (1994–1996)
In 1994, Stuart Murdoch and Stuart David both enrolled at Stow College's Beatbox programme for unemployed musicians in Glasgow. Together, with music professor Alan Rankine (formerly of the Associates), they recorded some demos, which in 1996 were picked up by the college's Music Business course that produces and releases one single each year on the college's label, Electric Honey. As Murdoch had a number of songs already and the label was extremely impressed with the demos, he was granted permission to record a full-length album, which was recorded mostly live over three days, entitled Tigermilk.

Murdoch and David recruited local musicians Stevie Jackson (guitar and vocals), Isobel Campbell (cello/vocals), Chris Geddes (keys) and Richard Colburn (drums), the latter of whom shared a flat with David and was a student on the Music Business course, to perform on the album, with Murdoch describing the process as a "product of botched capitalism". The band chose the name Belle and Sebastian from a short story Murdoch had written inspired by the television series Belle and Sebastian, about a six-year-old boy and his dog, named Belle, a Great Pyrenees. In June 1996, Electric Honey pressed up one thousand copies of Tigermilk on vinyl.

If You're Feeling Sinister and early EPs (1996–1998)
The warm response Tigermilk received led to the band being signed to Jeepster Records in August 1996, who released their second album If You're Feeling Sinister on 18 November. The album was named by Spin as one of the 100 greatest albums between 1985 and 2005, and it is widely considered the band's masterpiece. Just before the recording of Sinister, Sarah Martin (violin/vocals) joined the band.

Following this a series of EPs were released throughout 1997. The first of these was Dog on Wheels, released in May and consisting of four demo tracks recorded prior to the real formation of the band. In fact, the only long-term band members to play on the songs were Murdoch, David, and Mick Cooke, who played trumpet on the EP but would not officially join the band until a few years later. It charted at No. 59 in the UK singles chart. The Lazy Line Painter Jane EP followed in July. The track was recorded in the church where Murdoch lived and features vocals from Monica Queen. The EP narrowly missed out on the UK top 40, peaking at No. 41. The last of the EPs was October's 3.. 6.. 9 Seconds of Light. The EP was made Single of the Week in both the NME and Melody Maker and reached No. 32 in the charts, thus becoming the band's first top 40 single.

Despite the band's growing popularity, during this period they kept a low profile at the insistence of Murdoch, who was still regaining his strength following years struggling with myalgic encephalomyelitis/chronic fatigue syndrome (ME/CFS). The band played gigs sporadically, rarely gave interviews, and refused to appear in publicity photographs, often getting friends and acquaintances to pose instead. The relative reclusiveness helped to create an aura of mystique around them.

The Boy with the Arab Strap, Fold Your Hands Child, You Walk Like a Peasant and Line-up Changes (1998–2003)
The band released their third LP, The Boy with the Arab Strap in 1998, and it reached No. 12 in the UK charts. Arab Strap garnered an NPR interview and positive reviews from Rolling Stone and The Village Voice, and others; however, the album has its detractors, including Pitchfork, who gave the album a particularly poor review, calling it a "parody" of their earlier work (Pitchfork has since removed the review from their website and re-reviewed the album positively in 2018). During the recording of the album, long-time studio trumpet-player Mick Cooke was asked to join the band as a full member. The This Is Just a Modern Rock Song EP followed later that year.

In 1999, the band was awarded with Best Newcomer (for their third album) at the BRIT Awards, upsetting better-known acts such as Steps and 5ive. That same year, the band hosted their own festival, the Bowlie Weekender. Tigermilk was also given a full release by Jeepster before the band started work on their next LP. The result was Fold Your Hands Child, You Walk Like a Peasant, which became the band's first top 10 album in the UK, though critics felt that the band were starting to stagnate. A stand-alone single, "Legal Man", reached No. 15 and gave them their first appearance on Top of the Pops. As the band's popularity and recognition was growing worldwide, their music began appearing in films and on television. The 2000 film High Fidelity mentions the band (with Jack Black's character referring to them as "old sad bastard music" and disdaining their soft style) and features a clip from the song "Seymour Stein" from The Boy with the Arab Strap. Two songs by the band ("Expectations" and "Piazza, New York Catcher") appeared on the soundtrack for the 2007 hit film Juno. Also, the title track from Arab Strap was played over the end credits of the UK television series Teachers, and the lyric "Colour my life with the chaos of trouble" from the song was quoted by one of the characters in the 2009 film (500) Days of Summer.

Stuart David soon left the band to concentrate on his side project, Looper, and his book writing, which included his The Idle Thoughts of a Daydreamer. He was replaced by Bobby Kildea of V-Twin. The "Jonathan David" single, sung by Stevie Jackson, was released in June 2001 and was followed by "I'm Waking Up to Us" in November, which saw the band use an outside producer (Mike Hurst) for the first time. Most of 2002 was spent touring and recording a soundtrack album, Storytelling (for Storytelling by Todd Solondz). Campbell left the band in the spring of 2002, in the middle of the band's North American tour to pursue a solo career, first as The Gentle Waves, and later under her own name. She later collaborated with singer Mark Lanegan on three albums.

Dear Catastrophe Waitress, The Life Pursuit and hiatus (2003–2010)
The band left Jeepster in 2002, signing a four-album deal with Rough Trade Records. Their first album for Rough Trade, Dear Catastrophe Waitress, was released in 2003 and was produced by Trevor Horn. The album showed a markedly more "produced" sound compared to their first four LPs, as the band was making a concerted effort to produce more "radio-friendly" music. At this point, the band began to engage more with the press and started appearing in publicity shots. The album was warmly received and is credited with restoring the band's "indie cred". The album also marked the return of Murdoch as the group's primary songwriter, following the poorly received Fold Your Hands Child, You Walk Like a Peasant and Storytelling, both of which were more collaborative than the band's early work. A documentary DVD, Fans Only, was released by Jeepster in October 2003, featuring promotional videos, live clips and unreleased footage. A single from the album, "Step into My Office, Baby" followed in November 2003; it would be their first single to be taken from an album, and included a track recorded with Divine Comedy producer Darren Allison entitled Love on the March.

The Thin Lizzy-inspired "I'm a Cuckoo" was the second single from the album. It achieved their highest chart position yet, reaching No. 14 in the UK. The Books EP followed, a double A-side single led by "Wrapped Up in Books" from Dear Catastrophe Waitress and the new "Your Cover's Blown". This EP became the band's third top 20 UK release, and the band was nominated for both the Mercury Music Prize and an Ivor Novello Award. In January 2005, B&S was voted Scotland's greatest band in a poll by The List, beating Simple Minds, Idlewild, Travis, Franz Ferdinand, and The Proclaimers, among others.

In April 2005, members of the band visited Israel and the Palestinian territories with the UK charity War on Want; the group subsequently recorded a song inspired by the trip titled "The Eighth Station of the Cross Kebab House", which would first appear on the digital-download version of the charity album Help!: A Day in the Life and would later have a physical release as a B-side on 2006's "Funny Little Frog" single. Push Barman to Open Old Wounds, a compilation of the Jeepster singles and EPs, was released in May 2005 while the band were recording their seventh album in California. The result of the sessions was The Life Pursuit, produced by Tony Hoffer. The album, originally intended to be a double album, became the band's highest-charting album upon its release in February 2006, peaking at No. 8 in the UK and No. 65 on the US Billboard 200. "Funny Little Frog", which preceded it, also proved to be their highest-charting single, debuting at No. 13.

On 6 July 2006, the band played a historic show with the Los Angeles Philharmonic at the Hollywood Bowl. The opening act at the 18,000 seat sell-out concert was The Shins. The members of the band see this as a landmark event, with Stevie Jackson saying, "This is the biggest thrill of my entire life". In October 2006, members of the band helped put together a CD collection of new songs for children titled Colours Are Brighter, with the involvement of major bands such as Franz Ferdinand and The Flaming Lips.

On 18 November 2008 the band released The BBC Sessions, which features songs from the period of 1996–2001 (including the last recordings featuring Isobel Campbell before she left the band), along with a second disc featuring a recording of a live performance in Belfast from Christmas 2001.

Write About Love and Girls In Peacetime Want to Dance (2010–2016)
On 17 July 2010, the band performed their first UK gig in almost four years to a crowd of around 30,000 at Latitude Festival in Henham Park, Southwold. They performed two new songs, "I Didn't See It Coming" and "I'm Not Living in the Real World". Their eighth studio album, released in the UK and internationally on 25 September 2010, was titled Write about Love. The first single from the album, as well as the record's title track "Write about Love", was released in the US on 7 September 2010. Write about Love entered the UK albums chart in its first week of release, peaking at No. 8 as of 19 October 2010. Norah Jones is featured on the track "Little Lou, Ugly Jack, Prophet John", and Carey Mulligan sings on the title track.

In December 2010 Belle and Sebastian curated the sequel to the Bowlie Weekender in the form of Bowlie 2 presented by All Tomorrow's Parties.

In 2013, Pitchfork TV released an hour-long documentary in February, directed by RJ Bentler which focused on the band's 1996 album If You're Feeling Sinister, as well as the formation and early releases of the band. The documentary featured interviews with every member that was present on the album, as well as several archival photos and videos from the band's early days. The band compiled a second compilation album The Third Eye Centre which included the B-sides and rarities released after Push Barman to Open Old Wounds, from the albums Dear Catastrophe Waitress, The Life Pursuit, and Write about Love. In an interview at the end of 2013, Mick Cooke confirmed he had left the band on good terms.

The band received an 'Outstanding Contribution to Music Award' at the NME Awards 2014.

In 2014, the band returned to the studio, recording in Atlanta, Georgia for their ninth studio album, along with announcing tour dates for various festivals and concerts across the world during 2014. Their ninth album Girls in Peacetime Want to Dance was released on 19 January 2015. It was their first album with Dave McGowan, who had been their touring bassist since 2011.

The Belle and Sebastian song "There's Too Much Love" forms much of the soundtrack for the Brazilian film The Way He Looks, about a blind, gay teenage boy and his friends, released in 2014.

Belle and Sebastian performed at the Glastonbury Festival on 28 June 2015, on 'The Other Stage' and at O2 Academy, Glasgow in March 2017 which was televised in the UK as part of the 'BBC 6 MUSIC Presents Festival'.

How to Solve Our Human Problems, A Bit of Previous and Late Developers (2017–present)
In mid-2017, the band put out a new single, "We Were Beautiful". During the same year, the band appeared in the news for a comical story that occurred during their US tour, in which they accidentally forgot Colburn in a North Dakota Walmart. In December 2017 and January and February 2018, the band released a trio of EPs under the name How to Solve Our Human Problems.

On 3 November 2018, the band announced that Dave McGowan had become a member.

In August 2019, to celebrate the 20th anniversary of the first Bowlie Weekender festival, Belle & Sebastian held a third festival, dubbed the Boaty Weekender. Unlike the previous two festivals, the Boaty Weekender was held on a cruise ship in the Mediterranean Sea instead of UK holiday parks.

The band's eleventh studio album, A Bit of Previous, was released in May 2022.

In January 2023, the band announced the surprise release of their twelfth studio album, Late Developers. Lead single "I Don't Know What You See in Me" was released on 9 January 2023 with the album released on 13 January 2023.

Collaborations and side projects

 * The Reindeer Section were a Scottish indie rock supergroup formed in 2001 by Gary Lightbody of Snow Patrol, which released albums and gigged in 2001 and 2002. It featured Richard Colburn, Mick Cooke and Bobby Kildea from Belle and Sebastian.
 * The Vaselines are an alternative rock band formed in Glasgow in 1986. Between 2008 and 2014 their lineup featured Stevie Jackson and Bobby Kildea from Belle and Sebastian and they performed at Bowlie Weekender 2 curated by Belle and Sebastian in December 2010.
 * Tired Pony was a country / Americana supergroup formed by Gary Lightbody of Snow Patrol in 2010. It features Richard Colburn from Belle and Sebastian.
 * God Help the Girl is a musical project by Stuart Murdoch, featuring a group of female vocalists, including Catherine Ireton, with Belle and Sebastian as the accompanying band.
 * Looper is an electronic music group fronted by Stuart David.

Band members
Current members
 * Stuart Murdoch – vocals, guitar, keyboards (1996–present)
 * Stevie Jackson – guitar, vocals, piano (1996–present)
 * Sarah Martin – vocals, violin, guitar, flute, keyboards, recorder, percussion (1996–present)
 * Chris Geddes – keyboards, piano, percussion (1996–present)
 * Richard Colburn – drums, percussion (1996–present)
 * Bobby Kildea – guitar, bass (2001–present)
 * Dave McGowan – bass, keyboards, guitar (2018–present; touring musician 2012–2018)

Former members
 * Isobel Campbell – vocals, cello, guitar (1996–2002)
 * Stuart David – bass (1996–2000)
 * Mick Cooke – trumpet, guitar, bass, percussion (1998–2013; touring musician 1996–1998)

Timeline

Discography
Studio albums
 * Tigermilk (1996)
 * If You're Feeling Sinister (1996)
 * The Boy with the Arab Strap (1998)
 * Fold Your Hands Child, You Walk Like a Peasant (2000)
 * Storytelling (2002)
 * Dear Catastrophe Waitress (2003)
 * The Life Pursuit (2006)
 * Write About Love (2010)
 * Girls in Peacetime Want to Dance (2015)
 * Days of the Bagnold Summer (2019)
 * A Bit of Previous (2022)
 * Late Developers (2023)

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Belle and Sebastian


text:
Talk:Binary search

Primary Procedure can Yield Position in "unsuccessful" case
I observe that if the search terminates in Step 2 as "unsuccessful", the target value 'T' would be located between AR and AL. That is, R is the index (possibly -1) of the array element less than T and L is the index of the array element (possibly n) of the array element greater than T.

I find this property of the procedure useful when searching ranges. It is, I believe, one step faster than using the right-most or left-most variants on average.

I'm not sure if a note on the Article page is justified, but having this information would be helpful to those doing "range" searches. It may be that a note on the Article page violates some policy WRT cited work vs. original work, other Talk topics make me think it might.

This is not a comment on the utility of the left-most or right-most variants. They are useful when the array can contain duplicates. Usually no duplicates are present when the problem is to determine which range a value is in.

Glennp17321 (talk) 18:52, 17 May 2020 (UTC)

Ranges should have exclusive upper bounds
I've taught Binary Search multiple times at the university level. I've also asked it as an interview question about 50 times from people with Masters in CS. I've determined that a major reason that people fail my interview question is because binary search is usually taught with inclusive upper bounds, rather than exclusive ones. This Wikipedia article continues that habit. I think the article would be substantially improved by switching to exclusive upper bounds.

By "exclusive upper bounds", I mean that the initial state for an $$n$$ element array would become $$L=0$$ and $$R=n$$ instead of having $$R=n-1$$. Almost all good array code I've seen uses an exclusive upper bound. All of Java's libraries use an exclusive upper bound. One nice property of the exclusive upper bound is that $$R-L$$ is the number of items. A corollary is that $$L=R$$ is a test for an empty range and $$L<R$$ is a test for a non-empty one. Another good property of exclusive upper bounds is that for any $$M$$ where $$L$$≤$$M$$≤$$R$$, it is easy to split the range into two subranges $$[L,M)$$ and $$[M,R)$$. These properties make reasoning about the code much easier.

When you use the exclusive upper bound, the code for binary search becomes pretty natural:

function binary_search_exclusive_upper_bound(A, n, T) is L := 0 R := n    while R-L ≥ 2 do m := L + floor((R-L)/ 2) if T < A[m] then R := m        else: L := m    if R-L=1 and A[L] = T then return L    return unsuccessful

Nota Bene: I am assuming the "and" operator uses short-circuit evaluation.

Please compare the code above to the code on the main page. I hope you'll see that this code is much easier to reason about. You can see that (1) the loop runs only when it can split the range, (2) that $$m$$ is clearly not equal to $$R$$ and not equal to $$L$$, (3) that it doesn't matter if I used $$floor$$ or $$ceil$$ to compute $$m$$, (4) that range variables are correctly handled without off-by-one errors and (5) the code handles all cases, such as when $$n$$ is zero.

BTW, I believe that handling $$n$$ is zero, an empty range, is an important case. The paper by Pattis that is cited on the main page also considers it important. The main page's version of "binary_search_alternative" goes into an infinite loop if $$n$$ is zero. I see that as a consequence of using non-exclusive upper bounds, because the code on the main page is harder to reason about.

I believe binary search is usually taught with an inclusive upper bound because it is such an old algorithm. When it was created, we didn't have the habit (which I learned with C in the early 80's) of using an exclusive upper bound. But almost all array code now uses the exclusive upper bound. Using the exclusive upper bound is easier to reason with. I believe strongly that this article would be substantially improved by using exclusive upper bounds.

Michael Nahas, former Adjunct Faculty of University of Virginia, former Instructor at Johns Hopkins Center for Talented Youth

P.S. If you need an external reference, I wrote up my opinions on my website.

Mdnahas (talk) 23:07, 17 June 2021 (UTC)

 * Thank you very much for sharing your input! I definitely agree that the exclusive lower bound is a better and more logical way of implementing and reasoning about this algorithm. However, Wikipedia is not a place to "right great wrongs"; there at least needs to be a reference that confirms that this is actually the proper way to implement the algorithm. We can't use the thing you put on your website as a source, because it's self-published. Also, as you also mentioned, the inclusive upper bound is also still commonly used. I quickly looked up the .NET source code and it seems that they also use the inclusive upper bound in their binary search implementation (source). So I think that, if we were to add your version, the current one at least also needs to be mentioned, maybe under the "alternative procedure" section. ―Jochem van Hees (talk) 00:07, 19 June 2021 (UTC)

 * My quick impression is that having a half-open search range is likely to confuse more readers, when they start reading the article, than it helps later on with pseudocode simplifications. Also, my impression from other similar articles is that such a change is likely to lead to a nightmare of maintenance where we keep having to revert well-meaning freshmen who think they see an inconsistency in the inequalities and change it to look more consistent, without changing the rest of the code to match. So the situation is a little different from in a classroom, where you can control better the whole presentation. —David Eppstein (talk) 01:04, 19 June 2021 (UTC)

Using an exclusive upperbound is just good programming practice. I don't think I am trying to "right great wrongs" --- we're talking about adding 1 to a variable. I am just applying good practice to an algorithm. And, as I said, good practice is important to apply here. Many experienced programmers get this program wrong, because it is hard to reason about code that uses an inclusive upper bounds.

In fact, the exclusive upper bound is such good programming practice that C# version 8.0 has added a language feature where array ranges are specified with an exclusive upper bound.

Since Jochem looked up an implementation for the #5 programming language, let's look at what the other 4 do.

C's bsearch interface uses start + length. I couldn't find LLVM's implementation. The GCC implementation uses start + length.

The C++ STL function has an interface using exclusive upper bounds. The algorithm is implemented in std::lower_bound. The reference code works with start + length.

Python's bisect has an interface using an exclusive upper bound. It's implementation works using an exclusive upper bound.

Java's Arrays.binarySearch interface uses exclusive upper bounds. The OpenJDK implementation and Android implementation use an inclusive upper bound. The GNU implementation uses exclusive upper bounds.

I don't deny that the inclusive upper bound is used. It is how the literature first wrote about the algorithm. It is how most textbooks present it. It seems to be a leftover from before we knew that it was bad programming practice to use it. I'd like you to notice that none of these languages use the inclusive bounds for their interface. None. If there "needs to be a reference that confirms that this is actually the proper way to implement the algorithm", I would say that that is it.

I don't care if the Wikipedia page uses start+length or exclusive upper bounds. Either is fine programming practice. If David is worried about well-meaning freshman modifying code with the exclusive upper bounds, can we agree on start+length?

Mdnahas (talk) 19:09, 5 July 2021 (UTC)
 * If the inclusive upper bound is "how most textbooks present it" then that is a strong argument for how we should present it here. In this sort of thing, Wikipedia should be a follower, not a leader. —David Eppstein (talk) 19:39, 5 July 2021 (UTC)

 * Wikipedia "should be a follower" is an argument for Wikipedia not being a place for research or new scholarship. Changing a inclusive upper bound to start+length is not a new idea, nor is it significant to the algorithm itself.  Moreover, when saying "Wikipedia should be a follower", I think our reference should be the code being run, and not what's in textbooks.  That the code departs from the textbooks is an important detail, in my opinion.

 * I think the prime goal of Wikipedia is to clearly communicating an idea. I am confident that using an inclusive upper bound does not clearly communicate this algorithm. Mdnahas (talk) 17:07, 28 July 2021 (UTC)

 * Wikipedia is not the "place for research or new scholarship." No original research covers that. Wikipedia reports what reliable sources report. ~Anachronist (talk) 17:22, 28 July 2021 (UTC)

Apart from agreeing with David about following sources, I disagree with a lot that is written here. At the moment, what I think is being called the "inclusive" method, the upper and lower positions of where the target may be are treated the same. The algorithm in concept is symmetrical with respect to upper and lower. The proposed "exclusive" method proposes that the upper limit and the lower limit be treated differently, and this is claimed to be better. Well, BS. Adding extra concepts to an algorithm makes it harder to understand, not easier. I'm not convinced by the experience argument either, as I taught binary search to undergraduates more than 30 times without a similar experience. McKay (talk) 04:04, 29 July 2021 (UTC)

Approximate matches doesn't belong in this article
First of all, someone needs to define which regex means "Approximate matches"

I believe that they are exclusively talking about "begins with..." / "starts with..."

but it has almost nothing to do with binary searching. Even though it's interesting, it's not related to the Binary Search Algorithm.

AlwaysAngry (talk) 18:46, 25 November 2022 (UTC)

Examples of binary search described in ancient texts
Here are two instances of ancient texts that describe finding an item (person) in a list (group) by halving the size of the list in each iteration and examining a predicate over each. These instances may be earlier than the currently listed reference to sorted lists in a Babylonian tablet.

1. The Losaka story in the Jataka tales:

So in time it came to pass that the people fell into a wretched plight. Reflecting that such had not been their lot in former days, but that now they were going to rack and ruin, they concluded that there must be some breeder of misfortune among them, and resolved to divide into two bands. This they did; and there were then two bands of five hundred families each. Thence-forward, ruin dogged the band which included the parents of the future Losaka, whilst the other five hundred families throve apace. So the former resolved to go on halving their numbers, and did so, until this one family was parted from all the rest.

src: https://www.sacred-texts.com/bud/j1/j1044.htm

2. 1 Samuel 14:41 in the Old Testament, as described in Urim and Thummim.

src: https://en.wikisource.org/wiki/Bible_(King_James)/1_Samuel#14:41

- 152.44.156.175 (talk) 07:56, 4 July 2023 (UTC)

Section on galloping binary search?
Should we consider adding a section on galloping binary search, which operates differently, but it fundamentally the same algorithm? See for example Cormack's book on search systems. DMH43 (talk) 17:05, 29 December 2023 (UTC)

Requested move 1 June 2024

 * The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review after discussing it on the closer's talk page. No further edits should be made to this discussion.

The result of the move request was: moved. Favonian (talk) 20:43, 8 June 2024 (UTC)

Binary search algorithm → [[Binary search]]
The page was moved in 2005. I believe this extra word is not necessary. Here are what sources say:
 * CLRS vol. 1, 3rd edition
 * "binary search" 21 times (excluding 253 counts of "binary search tree")
 * of which "binary search algorithm" appears 2 times (upon first mention)

 * Programming Pearls
 * "binary search" 32 times (excluding 5 counts of "binary search tree")
 * no mention of "binary search algorithm"

 * TAOCP vol. 3 (searching and sorting), 2nd edition
 * "binary search" 62 times (excluding "binary search tree")
 * of which "binary search algorithm" 4 times,
 * and "binary search procedure" once.

IntGrah (talk) 20:42, 1 June 2024 (UTC) The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.
 * Support per nom. "Binary search" is clearly the WP:COMMONNAME and more WP:CONCISE. Malerisch (talk) 22:20, 1 June 2024 (UTC)
 * Support. I don't have strong feelings either way and I'm not convinced that one or the other is the common name, but more concise is better. —David Eppstein (talk) 22:28, 1 June 2024 (UTC)
 * Support: Commonly used, sufficiently clear, and more concise. — BarrelProof (talk) 18:24, 2 June 2024 (UTC)
 * Support. Clearly "algorithm" is necessary sometimes, such as to make clear that Floyd–Warshall is a graph algorithm and not a pop band or a law firm.  But it isn't as commonly used for algorithms such as binary search and long division. Quale (talk) 04:53, 3 June 2024 (UTC)

title: Talk:Binary search


text:
Broadcast domain

A broadcast domain is a logical division of a computer network, in which all nodes can reach each other by broadcast at the data link layer. A broadcast domain can be within the same LAN segment or it can be bridged to other LAN segments.

In terms of current popular technologies, any computer connected to the same Ethernet repeater or switch is a member of the same broadcast domain. Further, any computer connected to the same set of interconnected switches/repeaters is a member of the same broadcast domain. Routers and other higher-layer devices form boundaries between broadcast domains.

The notion of broadcast domain should be contrasted with that of collision domain, which would be all nodes on the same set of inter-connected repeaters, divided by switches and learning bridges. Collision domains are generally smaller than, and contained within, broadcast domains.

While some data-link-layer devices are able to divide the collision domains, broadcast domains are only divided by layer 3 network devices such as routers or layer 3 switches. Separating VLANs divides broadcast domains as well.

Further explanation
The distinction between broadcast and collision domains comes about because simple Ethernet and similar systems use a shared transmission system. In simple Ethernet (without switches or bridges), data frames are transmitted to all other nodes on a network. Each receiving node checks the destination address of each frame, and simply ignores any frame not addressed to its own MAC address or the broadcast address.

Switches act as buffers, receiving and analyzing the frames from each connected network segment. Frames destined for nodes connected to the originating segment are not forwarded by the switch. Frames destined for a specific node on a different segment are sent only to that segment. Only broadcast frames are forwarded to all other segments. This reduces unnecessary traffic and collisions.

In such a switched network, transmitted frames may not be received by all other reachable nodes. Nominally, only broadcast frames will be received by all other nodes. Collisions are localized to the physical-layer network segment they occur on. Thus, the broadcast domain is the entire inter-connected layer 2 network, and the segments connected to each switch/bridge port are each a collision domain. To clarify; repeaters do not divide collision domains but switches do. This means that since switches have become commonplace, collision domains are isolated to the specific half-duplex segment between the switch port and the connected node. Full-duplex segments, or links, don't form a collision domain as there is a dedicated channel between each transmitter and receiver, making collisions a thing of the past in modern wired networks.

In a switched network, enabling promiscuous mode for packet capturing results in no extra data being collected, as a NIC with promiscuous mode enabled simply neglects to drop Ethernet frames with a destination field populated with a MAC from another device. Such frames would not be forwarded by the switch to any ports on which that MAC is not communicating and with which it is associated in the MAC address table.

Not all network systems or media feature broadcast/collision domains. For example, PPP links.

Broadcast domain control
With a sufficiently sophisticated switch, it is possible to create a network in which the normal notion of a broadcast domain is strictly controlled. One implementation of this concept is termed a "private VLAN". Another implementation is possible with Linux and iptables. One analogy is that by creating multiple VLANs, the number of broadcast domains increases, but the size of each broadcast domain decreases. This is because a VLAN (or virtual LAN) is technically a broadcast domain.

This is achieved by designating one or more "server" or "provider" nodes, either by MAC address or switch port. Broadcast frames are allowed to originate from these sources and are sent to all other nodes. Broadcast frames from all other sources are directed only to the server/provider nodes. Traffic from other sources not destined to the server/provider nodes ("peer-to-peer" traffic) is blocked.

The result is a network based on a nominally shared transmission system; like Ethernet, but in which "client" nodes cannot communicate with each other, only with the server/provider. A common application is Internet providers. Allowing direct data link layer communication between customer nodes exposes the network to various security attacks, such as ARP spoofing. Controlling the broadcast domain in this fashion provides many of the advantages of a point-to-point network, using commodity broadcast-based hardware.

title: Broadcast domain


text:
Beechcraft

Beechcraft is an American brand of civil aviation and military aircraft owned by Textron Aviation since 2014, headquartered in Wichita, Kansas. Originally, it was a brand of Beech Aircraft Corporation, an American manufacturer of general aviation, commercial, and military aircraft, ranging from light single-engined aircraft to twin-engined turboprop transports, business jets, and military trainers. Beech later became a division of Raytheon and then Hawker Beechcraft before a bankruptcy sale turned its assets over to Textron (parent company of Beech's historical cross-town Wichita rival, Cessna Aircraft Company). It remains a brand of Textron Aviation.

History

Beech Aircraft Company was founded in Wichita, Kansas, in 1932 by Walter Beech as president, his wife Olive Ann Beech as secretary, Ted A. Wells as vice president of engineering, K. K. Shaul as treasurer, and investor C. G. Yankey as vice president. The company began operations in an idle Cessna factory. With designer Ted Wells, they developed the first aircraft under the Beechcraft name, the classic Beechcraft Model 17 Staggerwing, which first flew in November 1932. Over 750 Staggerwings were built, with 352 manufactured for the United States Army Air Forces and 67 for the United States Navy during World War II.

Beechcraft was not Beech's first company, as he had previously formed Travel Air in 1924 and the design numbers used at Beechcraft followed the sequence started at Travel Air, and were then continued at Curtiss-Wright, after Travel Air had been absorbed into the much larger company in 1929. Beech had become president of Curtiss-Wright's airplane division and VP of sales, but was dissatisfied with being so far removed from aircraft production. He quit to form Beechcraft, using the original Travel Air facilities and employing many of the same people. Model numbers prior to 11/11000 were built under the "Travel Air" name, while Curtiss-Wright built the CW-12, 14, 15, and 16 as well as previous successful Travel Air models (mostly the model 4).

In 1942 Beech won its first Army-Navy "E" Award production award and became one of the elite five percent of war contracting firms in the country to win five straight awards for production efficiency, mostly for the production of the Beechcraft Model 18 which remains in widespread use worldwide. Beechcraft ranked 69th among United States corporations in the value of World War II military production contracts.

After the war, the Staggerwing was replaced by the revolutionary Beechcraft Bonanza with a distinctive V-tail. Perhaps the best known Beech aircraft, the single-engined Bonanza has been manufactured in various models since 1947. The Bonanza has had the longest production run of any airplane, past or present, in the world. Other important Beech aircraft are the King Air and Super King Air line of twin-engined turboprops, in production since 1964, the Baron, a twin-engined variant of the Bonanza, and the Beechcraft Model 18, originally a business transport and commuter airliner from the late 1930s through the 1960s, which remains in active service as a cargo transport.

In 1950, Olive Ann Beech was installed as president and CEO of the company, after the sudden death of her husband from a heart attack on November 29 of that year. She continued as CEO until Beech was purchased by Raytheon Company on February 8, 1980. Ted Wells had been replaced as chief engineer by Herbert Rawdon, who remained at the post until his retirement in the early 1960s.

Throughout much of the mid-to-late 20th century, Beechcraft was considered one of the "Big Three" in the field of general aviation manufacturing, along with Cessna and Piper Aircraft.

In 1973, Beechcraft found Beechcraft Heritage Museum to host its historical aircraft.

In 1994, Raytheon merged Beechcraft with the Hawker product line it had acquired in 1993 from British Aerospace, forming Raytheon Aircraft Company. In 2002, the Beechcraft brand was revived to again designate the Wichita-produced aircraft. In 2006, Raytheon sold Raytheon Aircraft to Goldman Sachs creating Hawker Beechcraft. Since its inception Beechcraft has resided in Wichita, Kansas, also the home of chief competitor Cessna, the birthplace of Learjet and of Stearman, whose trainers were used in large numbers during WW II.

The entry into bankruptcy of Hawker Beechcraft on May 3, 2012 ended with its emergence on February 16, 2013 as a new entity, Beechcraft Corporation, with the Hawker Beechcraft name being retired. The new and much smaller company produce the King Air line of aircraft as well as the T-6 and AT-6 military trainer/attack aircraft, as well as the piston-powered single-engined Bonanza and twin-engined Baron aircraft. The jet line was discontinued, but the new company continues to support the aircraft already produced with parts, plus engineering and airworthiness documentation.

By October 2013, the company, now financially turned around, was up for sale.

On December 26, 2013, Textron agreed to purchase Beechcraft, including the discontinued Hawker jet line, for $1.4 billion. The sale was concluded in the first half of 2014, with government approval. Textron CEO Scott Donnelly indicated that Beechcraft and Cessna would be combined to form a new light aircraft manufacturing concern, Textron Aviation, that would result in US$65M–$85M in annual savings over keeping the companies separate. Textron has kept both the Beechcraft and Cessna names as separate brands.

Products

As of July 2019, Textron Aviation was producing the following models under the Beechcraft brand name:

 * Beechcraft Bonanza series – single-engined piston general aviation aircraft
 * Beechcraft Baron – twin-engined piston utility aircraft
 * Beechcraft Denali
 * (Super) King Air
 * C-12 Huron (military version)
 * Beechcraft T-6 Texan II/CT-156 Harvard II – single-engined turboprop military trainer, based on Pilatus PC-9

Facilities

 * Beech Factory Airport – houses Beechcraft's head office, manufacturing facility, and runway for test flights

title: Beechcraft