Binary search - Knowledge

7268:

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

11771: 6650:. 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. 11779: 8497: 6413: 3352: 3179: 3446: 6247:. 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 ( 38: 6670: 7134: 6875: 7312: 6744: 1066: 6224:) 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 8213:, 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. 185:. 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. 6140:

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

5203: 5243:. 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 8957:. When each subtree has a similar number of nodes, or equivalently the array is divided into halves in each iteration, the external nodes as well as their interior parent nodes lie within two levels. It follows that binary search minimizes the number of average comparisons as its comparison tree has the lowest possible internal path length. 6130: 4849: 4055:

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

6440:, 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 4916: 6139:

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

3341:

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

3210:

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

294:

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

6503:

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

3453:

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

4108:

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

6352:

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

6887:

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

1913:

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

7319:

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

7267:

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

4054:

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

6431:

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

6633:

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

6305:(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 6300:

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

8861:

length (the path length over all nodes where both children are present for each already-existing node) is minimized when the external nodes (the nodes with no children) lie within two consecutive levels of the tree. This also applies to internal paths as internal path length

7956:

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

11329: 6755:

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

3454:

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.

6403:

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.

263:, 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. 7118:

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.

3886: 6432:

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.

5875: 5803: 8828:

or simply one plus the average of all the internal path lengths of the tree. This is because internal paths represent the elements that the search algorithm compares to the target. The lengths of these internal paths represent the number of iterations

6724:

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

4653: 1845:, 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 8411: 5198:{\displaystyle 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} 4566: 11318: 4046: 9169:

units. Linear search has lower initial complexity because it requires minimal computation, but it quickly outgrows binary search in complexity. On the MIX computer, binary search only outperforms linear search with a sentinel if

6219:

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

4441:

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:

6882:

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

11362: 4437: 295:

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.

7416: 6435:

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

500: 6340:

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.

7722: 6504:

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.

9223:

This is because simply setting all of the bits which the hash functions point to for a specific key can affect queries for other keys which have a common hash location for one or more of the functions.

8717: 4067:

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

7522: 4171:. 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 9167: 4221:

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

7961:. 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 12117: 8833:

the root node. Adding the average of these lengths to the one iteration at the root yields the average case. Therefore, to minimize the average number of comparisons, the internal path length

7804: 4617: 422: 4113:

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

8421: 6860:

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.

5364: 6189: 3745: 3692: 3618: 3506: 7607: 6799: 3737: 6125:{\displaystyle 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)} 4327: 7032: 6838: 12102: 5518: 7895:

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

4133:, 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 3532: 12107: 8164: 11351: 9205:

Inserting the values in sorted order or in an alternating lowest-highest key pattern will result in a binary search tree that maximizes the average and worst-case search time.

8826: 8013: 2756: 2721: 2130: 2095: 1757:

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

1452: 1417: 1156: 780: 745: 7851:

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

6516:. 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 4332:

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

9013: 7841: 3931: 4844:{\displaystyle 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} 9055: 8756: 6680:

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

7113: 2868: 2248: 1570: 8630:. In Big O notation, the base of the logarithm does not matter since every logarithm of a given base is a constant factor of another logarithm of another base. That is, 5868: 3182:

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

2792: 2166: 1488: 898: 816: 7301: 6463:

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

3016: 229: 9106: 7242: 7644: 7181: 6401: 3049: 2378: 1674: 1355: 980: 8955: 6338: 3563: 2977: 2659: 2345: 2033: 683: 8624: 7880:, 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. 7546: 2405: 11855: 10432: 9194: 5834: 5511: 5298: 4909: 4880: 4646: 4268: 4094: 11006: 8039: 6939: 5436: 5390: 4215: 4157: 3333: 3278: 3117: 2947: 2916: 2212: 1641: 1534: 1326: 1230: 1206:) 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 944: 862: 654: 8343:, which implement general binary search, as well as specific implementations for searching slices of integers, floating-point numbers, and strings, respectively. 5482: 3439: 8920: 8900: 8880: 8851: 8789: 8600: 8210: 8188: 8122: 8100: 8079: 8059: 7742: 7072: 7052: 6959: 6913: 6702: 6619: 6551: 6298: 5459: 5410: 5269: 5225: 4350: 4239: 4189: 4131: 3306: 3252: 3200: 3138: 3090: 3069: 2889: 2832: 2812: 2682: 2630: 2610: 2590: 2570: 2509: 2489: 2465: 2445: 2425: 2315: 2290: 2269: 2186: 2056: 2004: 1984: 1964: 1944: 1843: 1694: 1610: 1590: 1508: 1378: 1300: 1280: 1260: 1204: 1184: 1044: 1024: 1000: 918: 836: 706: 628: 608: 588: 564: 544: 520: 341: 321: 249: 4447: 3419: 1911: 1823: 9601: 9599: 11438: 9597: 9595: 9593: 9591: 9589: 9587: 9585: 9583: 9581: 9579: 8973:

computer model, which Knuth designed as a representation of an ordinary computer, that the average running time of this variation for a successful search is

7201: 6858: 6590: 6458: 6209: 3936: 3641: 7145:

Fractional cascading is a technique that speeds up binary searches for the same element in multiple sorted arrays. Searching each array separately requires

3449:

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.

9576: 9863: 4059:

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.

9887: 7870:, 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 11113: 9505: 9503: 9501: 9499: 9497: 9495: 10652:

Childs, Andrew M.; Landahl, Andrew J.; Parrilo, Pablo A. (2007). "Quantum algorithms for the ordered search problem via semidefinite programming".

11296: 11266: 9875: 9057:

units for regular binary search. The time complexity for this variation grows slightly more slowly, but at the cost of higher initial complexity.

1232:). This results in a faster comparison loop, as one comparison is eliminated per iteration, while it requires only one more iteration on average. 9492: 7646:

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

4357: 10185: 10183: 10181: 10142: 6271:

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

7323: 10178: 7976:

In a practical implementation, the variables used to represent the indices will often be of fixed size (integers), and this can result in an

11232: 6191:

times in the worst case, the slight increase in efficiency per iteration does not compensate for the extra iteration for all but very large

11848: 11392: 7141:, 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. 11824: 9232:

There exist improvements of the Bloom filter which improve on its complexity or support deletion; for example, the cuckoo filter exploits

10360: 1914:

element of the value 4. The alternative procedure above will always return the index of the rightmost element if such an element exists.

9303: 9301: 270:

speeds up binary searches for the same value in multiple arrays. Fractional cascading efficiently solves a number of search problems in

12112: 10455: 9657: 9655: 7074:. When linear interpolation is used, and the distribution of the array elements is uniform or near uniform, interpolation search makes 427: 9423: 9421: 9419: 10775: 9298: 10195: 10154: 9652: 7548:

is the probability that the procedure yields the wrong position. The noisy binary search problem can be considered as a case of the

10003: 9416: 7657: 11841: 11816: 11064: 9793: 6572:

and multiple hash functions. Bloom filters are much more space-efficient than bit arrays in most cases and not much slower: with

10605:

Høyer, Peter; Neerbek, Jan; Shi, Yaoyun (2002). "Quantum complexities of ordered searching, sorting, and element distinctness".

8633: 4167:

In the binary tree representation, a successful search can be represented by a path from the root to the target node, called an

10081:. Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies. pp. 75–88. 9283: 6263:) which access elements in sequence. This adds slightly to the running time of binary search for large arrays on most systems. 11799: 11760: 11746: 11736: 11709: 11683: 11657: 11631: 11612: 11586: 11563: 11527: 11504: 11481: 10449: 10292: 7421: 10057: 6251:). On a sorted array, binary search can jump to distant memory locations if the array is large, unlike algorithms (such as 4051:

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

9115: 8364: 7320:

probability that controls the reliability of the yielded position. Every noisy binary search procedure must make at least

255:

except for small arrays. However, the array must be sorted first to be able to apply binary search. There are specialized

6622: 3569:. This is because the worst case is reached when the search reaches the deepest level of the tree, and there are always 10998: 9611: 8518: 7907:, increasing the average number of iterations by one, but reducing to one the number of comparisons per iteration. The 4573: 349: 8795:, the sum of the lengths of all internal paths. If each element is equally likely to be searched, the average case is 7751: 10825: 8358: 6684:

containing the differences is computed beforehand. For example, if the array to be searched is , the middle element (

6499:, are generally faster than binary search on a sorted array of records. Most hash table implementations require only 6437: 3881:{\displaystyle \lfloor \log _{2}(n)\rfloor +1-(2^{\lfloor \log _{2}(n)\rfloor +1}-\lfloor \log _{2}(n)\rfloor -2)/n} 11465: 10713: 10521: 10390: 10276: 7953: 11701: 11675: 11649: 7940:

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

6888:

target value is close to the highest element in the array, it is likely to be located near the end of the array.

6467:

generalizes this method of tree organization. B-trees are frequently used to organize long-term storage such as

6143: 3646: 3572: 3460: 11037: 6676:

stores the difference between the current and the two next possible middle elements instead of specific bounds.

5441:

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

5303: 3739:

iterations, which is one less than the worst case, if the search ends at the second-deepest level of the tree.

8480: – Algorithm for finding a zero of a function – the same idea used to solve equations in the real numbers 7567: 6759: 5798:{\displaystyle E(n)=I(n)+2n=\left+2n=(n+1)(\lfloor \log _{2}(n)\rfloor +2)-2^{\lfloor \log _{2}(n)\rfloor +1}} 4273: 4048:

iterations on average, assuming that the range between and outside elements is equally likely to be searched.

3697: 8428: 7654:

quantum binary search procedure—that is, a procedure that always yields the correct result—requires at least

6964: 6524:, with each bit representing a single key within the range of keys. Bit arrays are very fast, requiring only 3342:

should be considered to be part of the range and whether the array contains entries matching those endpoints.

3216: 9537: 9535: 9533: 6804: 12033: 12003: 11988: 9935: 9073:

computer, which Knuth designed as a representation of an ordinary computer, binary search takes on average

8483: 193: 130: 108: 90: 68: 11198: 8243:, which is typically implemented via binary search, although the official standard does not require it so. 138: 116: 98: 76: 11101: 9815: 9530: 8448: 8438: 8346: 7970: 7899:

published a binary search algorithm that worked on all arrays. In 1962, Hermann Bottenbruch presented an

2685: 2059: 1381: 1120: 709: 8128: 3511: 12122: 12058: 11932: 11922: 11902: 11553: 11288: 11254: 8767:

Any search algorithm based solely on comparisons can be represented using a binary comparison tree. An

7244:

by storing specific information in each array about each element and its position in the other arrays.

10910: 10849: 8798: 7983: 5366:, with the one iteration added to count the initial iteration. The external path length is divided by 2726: 2691: 2100: 2065: 1422: 1387: 1126: 750: 715: 11937: 10781: 10224: 10104: 9968: 9378: 8320: 6492: 6225: 3338:

The nearest neighbor of the target value is either its predecessor or successor, whichever is closer.

344: 19:

This article is about searching a finite sorted array. For searching continuous function values, see

11778: 11770: 10945: 10871: 10339: 10118: 9564: 8853:

must be minimized. It turns out that the tree for binary search minimizes the internal path length.

7813: 3891: 11051: 10021: 8976: 8272: 8229: 6513: 6302: 11220: 9851: 8722: 8509: 5227:, this is equivalent to the equation for the average case on a successful search specified above. 189: 12076: 12038: 11496: 9018: 7525: 6236: 3643:

is one less than a power of two, then this is always the case. Otherwise, the search may perform

3212: 2840: 2220: 1542: 11384: 9839: 9827: 8525: 8513: 7077: 5461:

nodes. For all binary trees, the external path length is equal to the internal path length plus

2764: 2138: 1460: 870: 788: 11882: 11821: 11046: 10866: 10424:"The Bayesian learner is optimal for noisy binary search (and pretty good for quantum as well)" 10334: 10319: 10113: 9070: 8970: 8250: 8169:

An infinite loop may occur if the exit conditions for the loop are not defined correctly. Once

7928: 7863: 7271: 7248: 6520:

is the simplest, useful when the range of keys is limited. It compactly stores a collection of

4110: 2982: 271: 199: 8435:

module that keeps a list in sorted order without having to sort the list after each insertion.

7810:

is the optimal quantum algorithm for searching an unordered list of elements, and it requires

11942: 11912: 10423: 9076: 8505: 7888: 7867: 7807: 7206: 6673: 6664: 6248: 3742:

On average, assuming that each element is equally likely to be searched, binary search makes

3356: 3021: 2350: 1646: 1334: 952: 9069:

performed a formal time performance analysis of both of these search algorithms. On Knuth's

8925: 8390:

versions of the binary search algorithm in its collection base classes. An example would be

7973:

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

7616: 7148: 6368: 2956: 2638: 2324: 2012: 662: 12053: 12028: 11973: 11541: 10671: 10591: 9757: 8609: 8350: 7924: 7896: 7531: 7138: 7128: 6892: 6879: 6869: 6308: 6244: 5839: 3541: 3234:

Predecessor queries can be performed with rank queries. If the rank of the target value is

2383: 267: 61: 5810: 5487: 5438:

external paths, representing the intervals between and outside the elements of the array.

5274: 4885: 4856: 4622: 4244: 4070: 3219:

seeking the number of elements between two values can be performed with two rank queries.

8: 12127: 12063: 12048: 11993: 9996: 9173: 8387: 8018: 7912: 6918: 5415: 5369: 4561:{\displaystyle \sum _{k=1}^{7}\left\lfloor \log _{2}(k)\right\rfloor =0+2(1)+4(2)=2+8=10} 4194: 4136: 3312: 3257: 3096: 2926: 2895: 2191: 1620: 1513: 1305: 1235: 1209: 923: 841: 633: 10999:"Extra, extra – read all about it: nearly all binary searches and mergesorts are broken" 10675: 9608:, §6.2.1 ("Searching an ordered table"), subsection "Further analysis of binary search". 5464: 3424: 12081: 11983: 11978: 11892: 11262: 11228: 10935: 10906: 10884: 10845: 10745: 10717: 10687: 10661: 10634: 10616: 10394: 10243: 10131: 10102:

Bloom, Burton H. (1970). "Space/time trade-offs in hash coding with allowable errors".

9746: 9728: 9697: 9480: 9453: 9405: 8905: 8885: 8865: 8836: 8774: 8585: 8240: 8195: 8173: 8107: 8085: 8064: 8044: 7920: 7892: 7057: 7037: 6944: 6898: 6748: 6738: 6687: 6635: 6500: 6484: 6424: 6416: 5444: 5395: 5254: 5210: 4335: 4224: 4174: 4116: 4041:{\displaystyle \lfloor \log _{2}(n)\rfloor +2-2^{\lfloor \log _{2}(n)\rfloor +1}/(n+1)} 3291: 3237: 3185: 3123: 3075: 3054: 2874: 2817: 2797: 2667: 2615: 2595: 2575: 2555: 2494: 2474: 2450: 2430: 2410: 2300: 2275: 2254: 2171: 2041: 1989: 1969: 1949: 1929: 1828: 1679: 1595: 1575: 1493: 1363: 1285: 1265: 1245: 1189: 1169: 1029: 1009: 985: 903: 821: 691: 613: 593: 573: 549: 529: 505: 326: 306: 279: 275: 234: 11147: 11060: 11029: 10563: 10546: 10320:"Lower bounds for intersection searching and fractional cascading in higher dimension" 9642: 9640: 9638: 8041:

may exceed the range of integers of the data type used to store the midpoint, even if

7727: 7315:

In noisy binary search, there is a certain probability that a comparison is incorrect.

6595: 6527: 6274: 3362: 1848: 1760: 1158:. This may change the result if the target value appears more than once in the array. 12043: 11887: 11795: 11787: 11756: 11732: 11705: 11679: 11653: 11627: 11608: 11582: 11578: 11559: 11523: 11500: 11477: 11426: 10964: 10821: 10490: 10473: 10445: 10352: 10288: 10270: 9899: 9472: 9397: 9345: 9267: 9214:

It is possible to search some hash table implementations in guaranteed constant time.

8550: 7876: 7745: 7647: 7610: 7256: 6565: 6354: 6240: 3694:

iterations if the search reaches the deepest level of the tree. However, it may make

1006:

This iterative procedure keeps track of the search boundaries with the two variables

10939: 10888: 10691: 10638: 10272:

Lower bounds for intersection searching and fractional cascading in higher dimension

10247: 9911: 9750: 9701: 9484: 9409: 8496: 12023: 12008: 11724: 11537: 11519: 11056: 10976: 10927: 10902: 10876: 10841: 10811: 10757: 10727: 10679: 10626: 10558: 10525: 10485: 10437: 10404: 10344: 10315: 10280: 10266: 10233: 10135: 10123: 10082: 9977: 9802: 9738: 9687: 9635: 9462: 9387: 9273: 8558: 8540: 8477: 8307:, that use binary search techniques by default for ranges that offer random access. 8222: 7977: 7966: 7916: 7553: 7186: 6843: 6726: 6575: 6443: 6194: 3888:

iterations when the target element is in the array. This is approximately equal to

3626: 3623:

The worst case may also be reached when the target element is not in the array. If

3566: 178: 158: 133: 51: 20: 10044: 9348: 11998: 11833: 11828: 10785: 10587: 10513: 10509: 10077:

Fan, Bin; Andersen, Dave G.; Kaminsky, Michael; Mitzenmacher, Michael D. (2014).

10053: 8416: 256: 111: 93: 71: 11082: 9884:, §6.2.2 ("Binary tree searching"), subsection "But what about the worst case?". 11864: 11549: 11473: 11109: 10683: 10348: 9953: 9512:, §6.2.1 ("Searching an ordered table"), subsection "History and bibliography". 9233: 8603: 8383: 7871: 7549: 6256: 3535: 1055: 11728: 10630: 9981: 9872:, §3.2 ("Binary Search Trees"), subsection "Order-based methods and deletion". 6412: 12096: 12013: 11822:

Comparisons and benchmarks of a variety of binary search implementations in C

11794:(4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. 11755:(4th ed.). Upper Saddle River, New Jersey: Addison-Wesley Professional. 11596: 10505: 10356: 10151:, §6.2.1 ("Searching an ordered table"), subsection "An important variation". 9963: 9959: 9476: 9401: 9109: 8554: 6496: 6349: 6252: 3933:

iterations. When the target element is not in the array, binary search makes

3351: 252: 16:

Search algorithm finding the position of a target value within a sorted array

10408: 10087: 8545: 3287:

can be used. If the result of running the procedure for the target value is

3178: 11963: 11927: 11897: 11693: 11667: 11641: 11518:. Software Engineering and Knowledge Engineering. Vol. 13. Singapore: 10994: 10918: 10857: 10607: 10192:, §6.2.1 ("Searching an ordered table"), subsection "Interpolation search". 9923: 9896:, §3.5 ("Applications"), "Which symbol-table implementation should I use?". 9807: 9788: 9489:

Procedure is described at p. 214 (§43), titled "Program for Binary Search".

7945: 7884: 7247:

Fractional cascading was originally developed to efficiently solve various

6681: 6561: 4432:{\displaystyle I(n)=\sum _{k=1}^{n}\left\lfloor \log _{2}(k)\right\rfloor } 3445: 182: 10731: 10530: 10284: 10238: 10215: 10127: 9692: 9675: 9467: 9448: 9392: 9373: 9278: 9272:. Proceedings of the 14th ACM Southeast Conference. ACM. pp. 95–101. 8562: 37: 11917: 11704:. Vol. 4A (1st ed.). Reading, MA: Addison-Wesley Professional. 10722: 10666: 10621: 10441: 9955: 9784: 8406: 8402: 7859: 7252: 6639: 6428: 6260: 6229: 3538:

that yields the greatest integer less than or equal to the argument, and

1166:

In the above procedure, the algorithm checks whether the middle element (

1050:

as follows, where the variable names and types remain the same as above,

260: 11678:. Vol. 3 (2nd ed.). Reading, MA: Addison-Wesley Professional. 11652:. Vol. 1 (3rd ed.). Reading, MA: Addison-Wesley Professional. 10980: 10816: 10799: 8512:). The updated content was reintegrated into the Knowledge page under a 7411:{\displaystyle (1-\tau ){\frac {\log _{2}(n)}{H(p)}}-{\frac {10}{H(p)}}} 6669: 2491:

in the array, or the number of elements in the array that are less than

42:

Visualization of the binary search algorithm where 7 is the target value

11907: 11545: 11359: 11326: 10931: 10880: 10761: 10705: 9325: 8233: 7133: 6874: 6554: 6488: 6472: 6362: 5271:

elements, which is a positive integer, and the external path length is

4241:

elements, which is a positive integer, and the internal path length is

1047: 523: 11750: 7311: 7251:

problems. Fractional cascading has been applied elsewhere, such as in

3154:

binary_search_rightmost(A, n, T): L := 0 R := n

11868: 11604: 10580:

Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei

9716: 9353: 8627: 8379: 7958: 6743: 6647: 6569: 6517: 6460:

comparisons. Binary search trees take more space than sorted arrays.

6358: 5251:

is the sum of the lengths of all unique external paths. If there are

5235:

Unsuccessful searches can be represented by augmenting the tree with

2524:

binary_search_leftmost(A, n, T): L := 0 R := n

1065: 251:

is the number of elements in the array. Binary search is faster than

9742: 9554: 9552: 9550: 9310:, §6.2.1 ("Searching an ordered table"), subsection "Binary search". 8486: – Binary search variation with simplified midpoint calculation 8125:

are nonnegative, this can be avoided by calculating the midpoint as

7980:

for very large arrays. If the midpoint of the span is calculated as

6232:) is often more expensive than comparing integers or short strings. 2548:

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

1238:

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

10399: 9733: 9520: 9518: 7900: 7891:, a seminal and foundational college course in computing. In 1957, 6468: 5300:, then the average number of iterations for an unsuccessful search 4097: 1922:

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

1062:

refers to a specific value that conveys the failure of the search.

10204:, §6.2.1 ("Searching an ordered table"), subsection "Exercise 22". 10163:, §6.2.1 ("Searching an ordered table"), subsection "Algorithm U". 9966:(August 1994). "Dynamic perfect hashing: upper and lower bounds". 9664:, §6.2.1 ("Searching an ordered table"), subsection "Exercise 23". 9430:, §6.2.1 ("Searching an ordered table"), subsection "Algorithm B". 9108:

units of time for a successful search, while linear search with a

12018: 9789:"Optimal bounds for the predecessor problem and related problems" 9547: 9269:

A modification to the half-interval search (binary search) method

7748:. There is an exact quantum binary search procedure that runs in 6564:, another probabilistic data structure based on hashing, store a 495:{\displaystyle A_{0}\leq A_{1}\leq A_{2}\leq \cdots \leq A_{n-1}} 11817:

NIST Dictionary of Algorithms and Data Structures: binary search

9515: 5870:, the average case for unsuccessful searches can be determined: 4270:, then the average number of iterations for a successful search 3284: 11190: 11172: 10385:

Emamjomeh-Zadeh, Ehsan; Kempe, David; Singhal, Vikrant (2016).

10076: 6464: 4329:, with the one iteration added to count the initial iteration. 3224: 3211:(next-smallest element), successor (next-largest element), and 283: 266:

There are numerous variations of binary search. In particular,

12118:

Knowledge articles published in peer-reviewed literature (W2J)

11601:

A practical guide to data structures and algorithms using Java

10547:"Searching games with errors—fifty years of coping with liars" 9313: 7203:

is the number of arrays. Fractional cascading reduces this to

6708:. In this case, the middle element of the left subarray () is 2543: 8412:

NSArray -indexOfObject:inSortedRange:options:usingComparator:

8372:

package for performing binary searches on Java arrays and on

8310: 8246: 7717:{\textstyle {\frac {1}{\pi }}(\ln n-1)\approx 0.22\log _{2}n} 7564:

Classical computers are bounded to the worst case of exactly

3359:

representing binary search. The array being searched here is

3119:

is the number of elements in the array that are greater than

1917: 1704:

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

10578:

Rényi, Alfréd (1961). "On a problem in information theory".

8317:

verb for performing binary searches on COBOL ordered tables.

11947: 10384: 6643: 3148:

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

2518:

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

11536: 10778: 10166: 9331: 8712:{\displaystyle \log _{b}(n)=\log _{k}(n)\div \log _{k}(b)} 11407: 11128: 6521: 6419:

are searched using an algorithm similar to binary search.

6221: 12103:

Knowledge articles published in peer-reviewed literature

10504: 9719:(2017). "Array Layouts for Comparison-Based Searching". 6961:

is the target, then the target is estimated to be about

6751:

finding the upper bound for the subsequent binary search

4619:

based on the equation for the average case. The sum for

10850:"Fractional cascading: I. A data structuring technique" 10710:

A fast quantum mechanical algorithm for database search

10387:

Deterministic and probabilistic binary search in graphs

7887:

made the first mention of binary search as part of the

7613:

for binary search are still bounded to a proportion of

7517:{\displaystyle H(p)=-p\log _{2}(p)-(1-p)\log _{2}(1-p)} 6801:

iterations before binary search is started and at most

6134: 3158:L < R: m := floor((L + R) / 2) 2528:L < R: m := floor((L + R) / 2) 12108:

Knowledge articles published in WikiJournal of Science

9374:"Average binary search length for dense ordered lists" 9343: 9176: 9118: 9079: 9021: 8979: 7754: 7730: 7660: 7619: 7570: 7209: 7189: 7151: 7080: 6846: 6807: 6762: 6598: 6578: 6530: 6446: 6371: 6311: 6277: 6197: 6146: 3700: 3649: 3629: 3575: 3544: 3514: 3463: 2723:, which is the greatest integer less than or equal to 2097:, which is the greatest integer less than or equal to 1419:, which is the least integer greater than or equal to 747:, which is the greatest integer less than or equal to 9676:"Analytic derivation of comparisons in binary search" 9620:, §6.2.1 ("Searching an ordered table"), "Theorem B". 9162:{\textstyle 1.75n+8.5-{\frac {n{\text{ mod }}2}{4n}}} 8928: 8908: 8888: 8868: 8839: 8801: 8777: 8725: 8636: 8612: 8588: 8198: 8176: 8131: 8110: 8088: 8067: 8047: 8021: 7986: 7969:

that remained undetected for over twenty years. The

7816: 7534: 7424: 7326: 7274: 7060: 7040: 6967: 6947: 6921: 6901: 6690: 6266: 5878: 5842: 5813: 5521: 5490: 5467: 5447: 5418: 5398: 5372: 5306: 5277: 5257: 5213: 4919: 4888: 4859: 4656: 4625: 4576: 4450: 4360: 4338: 4276: 4247: 4227: 4197: 4177: 4139: 4119: 4073: 3939: 3894: 3748: 3427: 3365: 3315: 3294: 3260: 3240: 3188: 3126: 3099: 3078: 3057: 3024: 2985: 2959: 2929: 2898: 2877: 2843: 2820: 2800: 2767: 2729: 2694: 2670: 2641: 2618: 2598: 2578: 2558: 2497: 2477: 2453: 2433: 2413: 2386: 2353: 2327: 2303: 2278: 2257: 2223: 2194: 2174: 2141: 2103: 2068: 2044: 2015: 1992: 1972: 1952: 1932: 1851: 1831: 1763: 1682: 1649: 1623: 1598: 1578: 1545: 1516: 1496: 1463: 1425: 1390: 1366: 1337: 1308: 1288: 1268: 1248: 1212: 1192: 1172: 1129: 1032: 1012: 988: 955: 926: 906: 873: 844: 824: 791: 753: 718: 694: 665: 636: 616: 596: 576: 552: 532: 508: 430: 352: 329: 309: 237: 202: 10651: 9623: 8771:is any path from the root to an existing node. Let 6712:and the middle element of the right subarray () is 4109:unsuccessful searches, it will be assumed that the 1696:. Otherwise, the search terminates as unsuccessful. 181:that finds the position of a target value within a 11863: 10261: 10259: 10257: 9367: 9365: 9188: 9161: 9100: 9049: 9007: 8949: 8914: 8894: 8874: 8845: 8820: 8783: 8750: 8711: 8618: 8594: 8204: 8182: 8158: 8116: 8094: 8073: 8053: 8033: 8007: 7835: 7798: 7736: 7716: 7638: 7601: 7540: 7516: 7410: 7295: 7236: 7195: 7175: 7107: 7066: 7046: 7026: 6953: 6933: 6907: 6852: 6832: 6793: 6696: 6613: 6584: 6545: 6452: 6395: 6332: 6292: 6228:values (the most common digital representation of 6203: 6183: 6124: 5862: 5828: 5797: 5505: 5476: 5453: 5430: 5404: 5384: 5358: 5292: 5263: 5219: 5197: 4903: 4874: 4843: 4640: 4611: 4560: 4431: 4344: 4321: 4262: 4233: 4209: 4183: 4151: 4125: 4088: 4040: 3925: 3880: 3731: 3686: 3635: 3612: 3557: 3526: 3500: 3433: 3413: 3327: 3300: 3272: 3246: 3194: 3132: 3111: 3084: 3063: 3043: 3010: 2971: 2941: 2910: 2883: 2862: 2826: 2806: 2786: 2750: 2715: 2676: 2653: 2624: 2604: 2584: 2564: 2503: 2483: 2459: 2439: 2419: 2399: 2372: 2339: 2309: 2284: 2263: 2242: 2206: 2180: 2160: 2124: 2089: 2050: 2027: 1998: 1978: 1958: 1938: 1905: 1837: 1817: 1688: 1668: 1635: 1604: 1584: 1564: 1528: 1502: 1482: 1446: 1411: 1372: 1349: 1320: 1294: 1274: 1254: 1224: 1198: 1178: 1150: 1038: 1018: 994: 974: 938: 912: 892: 856: 830: 810: 774: 739: 700: 677: 648: 622: 602: 582: 558: 538: 514: 494: 416: 335: 315: 243: 223: 11621: 11490: 9962:; Meyer auf der Heide, Friedhelm; Rohnert, Hans; 9824:, Answers to Exercises (§6.2.1) for "Exercise 5". 9524: 9442: 9440: 9438: 9436: 9372:Flores, Ivan; Madpis, George (1 September 1971). 9319: 7927:as a method to solve numerous search problems in 7799:{\textstyle 4\log _{605}n\approx 0.433\log _{2}n} 6941:are the lower and upper bounds respectively, and 6716:. Uniform binary search would store the value of 5247:is a path from the root to an external node. The 4612:{\displaystyle 1+{\frac {10}{7}}=2{\frac {3}{7}}} 3309:, then the successor of the target value is 417:{\displaystyle A_{0},A_{1},A_{2},\ldots ,A_{n-1}} 12094: 11723:. Hamburg, Germany: Kluwer Academic Publishers. 11622:Kasahara, Masahiro; Morishita, Shinichi (2006). 10748:(1957). "Addressing for random-access storage". 8327:standard library package contains the functions 7903:implementation of binary search that placed the 6592:hash functions, membership queries require only 11491:Butterfield, Andrew; Ngondi, Gerard E. (2016). 10967:(1988). "Textbook errors in binary searching". 10797: 10604: 10308: 10254: 10214:Perl, Yehoshua; Itai, Alon; Avni, Haim (1978). 10072: 10070: 9362: 11745: 11595: 11259:Java Platform Standard Edition 8 Documentation 11225:Java Platform Standard Edition 8 Documentation 10901: 10840: 10804:Proceedings of Symposia in Applied Mathematics 10518:Coping with errors in binary search procedures 10421: 9893: 9869: 9857: 9570: 9558: 9541: 9433: 3231:the target value is returned by the procedure. 2532:A < T: L := m + 1 278:extends binary search to unbounded lists. The 11849: 10800:"Teaching combinatorial tricks to a computer" 9265: 9245:That is, arrays of length 1, 3, 7, 15, 31 ... 6214: 4103: 3508:iterations of the comparison loop, where the 11718: 10433:Symposium on Foundations of Computer Science 10422:Ben-Or, Michael; Hassidim, Avinatan (2008). 10213: 10172: 10079:Cuckoo filter: practically better than Bloom 10067: 10038: 10036: 9371: 8882:is linearly related to external path length 7596: 7571: 6827: 6808: 6788: 6763: 6507: 6178: 6147: 6091: 6066: 6049: 6024: 5990: 5965: 5945: 5920: 5784: 5759: 5739: 5714: 5175: 5150: 5136: 5111: 5091: 5066: 4007: 3982: 3965: 3940: 3858: 3833: 3819: 3794: 3774: 3749: 3726: 3701: 3681: 3650: 3607: 3576: 3521: 3515: 3495: 3464: 2684:(the position of the middle element) to the 2058:(the position of the middle element) to the 1380:(the position of the middle element) to the 708:(the position of the middle element) to the 286:data structures are based on binary search. 11558:(3rd ed.). MIT Press and McGraw-Hill. 11030:"On computing the semi-sum of two integers" 10645: 10314: 10265: 10030:, §7.1.3 ("Bitwise Tricks and Techniques"). 9714: 9446: 9259: 7262: 6184:{\textstyle \lfloor \log _{2}(n)+1\rfloor } 3687:{\textstyle \lfloor \log _{2}(n)+1\rfloor } 3613:{\textstyle \lfloor \log _{2}(n)+1\rfloor } 3501:{\textstyle \lfloor \log _{2}(n)+1\rfloor } 3285:procedure for finding the rightmost element 2544:Procedure for finding the rightmost element 11856: 11842: 11786: 11572: 11413: 11177:COBOL ANSI-85 programming reference manual 11134: 10954:, §4.1 ("The Challenge of Binary Search"). 8522:). The version of record as reviewed is: 8445:method with built-in approximate matching. 7908: 7904: 7806:queries in the worst case. In comparison, 7609:iterations when performing binary search. 4570:The average number of iterations would be 3620:levels in the tree for any binary search. 3225:procedure for finding the leftmost element 3162:A > T: R := m 1918:Procedure for finding the leftmost element 1714:L := 0 R := n − 1 1119:Alternatively, the algorithm may take the 1080:L := 0 R := n − 1 36: 11719:Moffat, Alistair; Turpin, Andrew (2002). 11385:"8.6. bisect — Array bisection algorithm" 11050: 10870: 10815: 10721: 10665: 10620: 10562: 10529: 10489: 10398: 10338: 10237: 10117: 10086: 10033: 9944:, §6.4 ("Hashing"), subsection "History". 9806: 9782: 9732: 9691: 9466: 9391: 9277: 9266:Williams, Jr., Louis F. (22 April 1976). 8544: 7602:{\textstyle \lfloor \log _{2}n+1\rfloor } 6794:{\textstyle \lfloor \log _{2}x+1\rfloor } 6621:time. However, Bloom filters suffer from 6353:array needs to be sorted beforehand. All 5359:{\displaystyle T'(n)={\frac {E(n)}{n+1}}} 3732:{\textstyle \lfloor \log _{2}(n)\rfloor } 11102:"bsearch – binary search a sorted table" 11027: 10957: 10911:"Fractional cascading: II. Applications" 10744: 10474:"Searching with known error probability" 10465: 9848:, §5.3.1 ("Minimum-Comparison sorting"). 9836:, §6.2.1 ("Searching an ordered table"). 9544:, §3.1, subsection "Rank and selection". 8524:Anthony Lin; et al. (2 July 2019). 7934: 7559: 7310: 7132: 6873: 6742: 6668: 6658: 6628: 6411: 5230: 4322:{\displaystyle T(n)=1+{\frac {I(n)}{n}}} 3444: 3350: 3177: 2468: 1161: 1064: 685:, the search terminates as unsuccessful. 526:uses binary search to find the index of 11464: 11289:"List<T>.BinarySearch method (T)" 11088: 11021: 10951: 10750:IBM Journal of Research and Development 10327:Journal of Computer and System Sciences 10042: 9794:Journal of Computer and System Sciences 9778: 9776: 9774: 9772: 8490: 8396:BinarySearch<T>(T array, T value) 7122: 7027:{\displaystyle (T-A_{L})/(A_{R}-A_{L})} 6863: 6840:iterations of the binary search, where 6833:{\textstyle \lfloor \log _{2}x\rfloor } 3457:In the worst case, binary search makes 3223:Rank queries can be performed with the 12095: 11626:. London, UK: Imperial College Press. 11624:Large-scale genome sequence processing 11171: 10963: 10716:. Philadelphia, PA. pp. 212–219. 10704: 7306: 4162: 3173: 11837: 11692: 11666: 11640: 11513: 10993: 10577: 10201: 10189: 10160: 10148: 10101: 10027: 9941: 9929: 9917: 9905: 9881: 9845: 9833: 9821: 9763: 9673: 9661: 9646: 9629: 9617: 9605: 9509: 9447:Bottenbruch, Hermann (1 April 1962). 9427: 9344: 9307: 9066: 8966: 8854: 6732: 6568:of keys by encoding the keys using a 6491:, a data structure that maps keys to 6357:based on comparing elements, such as 3051:is the rightmost element that equals 1752: 1088:m := floor((L + R) / 2) 259:designed for fast searching, such as 11148:"std.range - D Programming Language" 10714:ACM Symposium on Theory of Computing 10544: 10522:ACM Symposium on Theory of Computing 10471: 10461:from the original on 9 October 2022. 10391:ACM Symposium on Theory of Computing 10277:ACM Symposium on Theory of Computing 9769: 9721:Journal of Experimental Algorithmics 6634:specialized data structures such as 6235:On most computer architectures, the 6135:Performance of alternative procedure 4217:counting the initial iteration. The 2407:is the leftmost element that equals 1722:m := ceil((L + R) / 2) 1046:. The procedure may be expressed in 10366:from the original on 9 October 2022 10063:from the original on 9 October 2022 10009:from the original on 9 October 2022 9766:, §2.2.2 ("Sequential Allocation"). 9573:, §3.1, subsection "Range queries". 6891:A common interpolation function is 4062: 3527:{\textstyle \lfloor \cdot \rfloor } 1710:binary_search_alternative(A, n, T) 13: 11395:from the original on 25 March 2018 11365:from the original on 20 April 2016 11332:from the original on 17 April 2016 11269:from the original on 23 April 2016 11235:from the original on 29 April 2016 11201:from the original on 25 April 2016 11116:from the original on 21 March 2016 11106:The Open Group Base Specifications 9286:from the original on 12 March 2017 8415:method in Mac OS X 10.6+. Apple's 8216: 8159:{\displaystyle L+{\frac {R-L}{2}}} 7911:was developed by A. K. Chandra of 7905:comparison for equality at the end 6267:Binary search versus other schemes 3206:The above procedure only performs 3166:: L := m + 1 14: 12139: 12113:Externally peer reviewed articles 11810: 11721:Compression and coding algorithms 11009:from the original on 1 April 2016 9994: 9860:, §3.2 ("Ordered symbol tables"). 7858:. The tablet contained about 500 7724:queries in the worst case, where 6557:handles 64-bit keys efficiently. 11777: 11769: 11493:A dictionary of computer science 11070:from the original on 3 July 2006 10216:"Interpolation search—a log log 8821:{\displaystyle 1+{\frac {I}{n}}} 8495: 8225:include binary search routines: 8008:{\displaystyle {\frac {L+R}{2}}} 7556:where the answers may be wrong. 6344: 5484:. Substituting the equation for 2751:{\displaystyle {\frac {L+R}{2}}} 2716:{\displaystyle {\frac {L+R}{2}}} 2125:{\displaystyle {\frac {L+R}{2}}} 2090:{\displaystyle {\frac {L+R}{2}}} 1447:{\displaystyle {\frac {L+R}{2}}} 1412:{\displaystyle {\frac {L+R}{2}}} 1151:{\displaystyle {\frac {L+R}{2}}} 775:{\displaystyle {\frac {L+R}{2}}} 740:{\displaystyle {\frac {L+R}{2}}} 11702:The Art of Computer Programming 11676:The Art of Computer Programming 11650:The Art of Computer Programming 11419: 11377: 11344: 11311: 11299:from the original on 7 May 2016 11281: 11247: 11213: 11183: 11179:, vol. 1, pp. 598–601 11165: 11140: 11094: 10987: 10895: 10834: 10791: 10768: 10738: 10698: 10598: 10571: 10538: 10498: 10415: 10378: 10207: 10095: 9988: 9947: 9708: 9667: 9449:"Structure and use of ALGOL 60" 9239: 9226: 9217: 9208: 9199: 9060: 8960: 8761: 8275:'s standard library Phobos, in 6512:A related problem to search is 11599:; Goldman, Kenneth J. (2008). 11516:Data structures and algorithms 11391:. Python Software Foundation. 11038:Information Processing Letters 9337: 9008:{\textstyle 17.5\log _{2}n+17} 8745: 8739: 8706: 8700: 8681: 8675: 8656: 8650: 8576: 8500:This article was submitted to 8356:static methods in the classes 7836:{\displaystyle O({\sqrt {n}})} 7830: 7820: 7689: 7671: 7511: 7499: 7483: 7471: 7465: 7459: 7434: 7428: 7418:comparisons on average, where 7402: 7396: 7378: 7372: 7364: 7358: 7339: 7327: 7290: 7278: 7231: 7213: 7170: 7155: 7102: 7084: 7021: 6995: 6987: 6968: 6608: 6602: 6540: 6534: 6390: 6375: 6327: 6315: 6287: 6281: 6169: 6163: 6119: 6107: 6088: 6082: 6046: 6040: 6015: 6003: 5987: 5981: 5954: 5942: 5936: 5917: 5914: 5902: 5893: 5887: 5857: 5851: 5823: 5817: 5807:Substituting the equation for 5781: 5775: 5748: 5736: 5730: 5711: 5708: 5696: 5657: 5645: 5611: 5599: 5578: 5566: 5546: 5540: 5531: 5525: 5500: 5494: 5339: 5333: 5321: 5315: 5287: 5281: 5184: 5172: 5166: 5133: 5127: 5103: 5088: 5082: 5035: 5023: 4989: 4977: 4956: 4944: 4929: 4923: 4898: 4892: 4869: 4863: 4853:Substituting the equation for 4819: 4807: 4773: 4761: 4740: 4728: 4717: 4711: 4666: 4660: 4635: 4629: 4537: 4531: 4522: 4516: 4496: 4490: 4421: 4415: 4370: 4364: 4310: 4304: 4286: 4280: 4257: 4251: 4083: 4077: 4035: 4023: 4004: 3998: 3962: 3956: 3926:{\displaystyle \log _{2}(n)-1} 3914: 3908: 3867: 3855: 3849: 3816: 3810: 3786: 3771: 3765: 3723: 3717: 3672: 3666: 3598: 3592: 3486: 3480: 3408: 3366: 3346: 2536:: R := m 1900: 1852: 1812: 1764: 1734:: L := m 1730:R := m − 1 1104:R := m − 1 274:and in numerous other fields. 218: 206: 1: 11061:10.1016/S0020-0190(03)00263-1 10564:10.1016/S0304-3975(01)00303-6 9908:, §5.4.9 ("Disks and Drums"). 9525:Kasahara & Morishita 2006 9320:Butterfield & Ngondi 2016 9112:at the end of the list takes 7852: 6653: 982:, the search is done; return 11792:The C++ programming language 11573:Fitzgerald, Michael (2015). 11495:(7th ed.). Oxford, UK: 11028:Ruggieri, Salvatore (2003). 10551:Theoretical Computer Science 10491:10.1016/0304-3975(89)90077-7 10478:Theoretical Computer Science 10318:; Liu, Ding (1 March 2004). 9920:, §6.2.4 ("Multiway trees"). 9252: 9050:{\textstyle 18\log _{2}n-16} 8751:{\displaystyle \log _{k}(b)} 8484:Multiplicative binary search 8451:'s slice primitive provides 8419:C framework also contains a 6720:as both indices differ from 6438:balanced binary search trees 3202:, which is not in the array. 298: 289: 7: 11389:The Python Standard Library 11293:Microsoft Developer Network 11195:The Go Programming Language 10269:; Liu, Ding (6 July 2001). 9649:, §2.3.4.5 ("Path length"). 8471: 7303:queries in the worst case. 7108:{\textstyle O(\log \log n)} 3283:For successor queries, the 2863:{\displaystyle A_{m}\leq T} 2243:{\displaystyle A_{m}\geq T} 1565:{\displaystyle A_{m}\leq T} 10: 12144: 11577:. Sebastopol, California: 11555:Introduction to algorithms 11457: 10684:10.1103/PhysRevA.75.032335 10349:10.1016/j.jcss.2003.07.003 9894:Sedgewick & Wayne 2011 9870:Sedgewick & Wayne 2011 9858:Sedgewick & Wayne 2011 9674:Rolfe, Timothy J. (1997). 9571:Sedgewick & Wayne 2011 9559:Goldman & Goldman 2008 9542:Sedgewick & Wayne 2011 9015:units of time compared to 8441:'s Array class includes a 7846: 7126: 6867: 6736: 6662: 6478: 6215:Running time and cache use 4352:nodes, which is equal to: 4104:Derivation of average case 3421:, and the target value is 3254:, its predecessor is 2787:{\displaystyle A_{m}>T} 2161:{\displaystyle A_{m}<T} 1483:{\displaystyle A_{m}>T} 1186:) is equal to the target ( 893:{\displaystyle A_{m}>T} 811:{\displaystyle A_{m}<T} 18: 12072: 11956: 11875: 11827:25 September 2019 at the 11729:10.1007/978-1-4615-0935-6 11435:The Rust Standard Library 10631:10.1007/s00453-002-0976-3 10279:. ACM. pp. 322–329. 10225:Communications of the ACM 10105:Communications of the ACM 9982:10.1137/S0097539791194094 9969:SIAM Journal on Computing 9379:Communications of the ACM 9236:to gain these advantages. 8526:"Binary search algorithm" 8081:are within the range. If 7971:Java programming language 7296:{\displaystyle O(\log n)} 6560:For approximate results, 6553:time. The Judy1 type of 6508:Set membership algorithms 3227:. The number of elements 3011:{\displaystyle A_{R-1}=T} 1643:, the search is done. If 224:{\displaystyle O(\log n)} 147: 129: 107: 89: 67: 57: 47: 35: 11698:Combinatorial algorithms 10798:Lehmer, Derrick (1960). 10788:. Retrieved 7 May 2016. 10746:Peterson, William Wesley 10173:Moffat & Turpin 2002 9954:Dietzfelbinger, Martin; 9101:{\textstyle 18\log n-16} 8569: 8291:functions) with methods 7263:Generalization to graphs 7237:{\textstyle O(k+\log n)} 6407: 1096:L := m + 1 343:elements with values or 12077:List of data structures 11749:; Wayne, Kevin (2011). 11603:. Boca Raton, Florida: 11514:Chang, Shi-Kuo (2003). 11497:Oxford University Press 11255:"java.util.Collections" 10409:10.1145/2897518.2897656 10088:10.1145/2674005.2674994 8409:framework provides the 8279:module provides a type 8253:provides the functions 7893:William Wesley Peterson 7639:{\textstyle \log _{2}n} 7526:binary entropy function 7176:{\textstyle O(k\log n)} 6396:{\textstyle O(n\log n)} 3044:{\displaystyle A_{R-1}} 2373:{\displaystyle A_{L}=T} 1669:{\displaystyle A_{L}=T} 1350:{\displaystyle L\neq R} 1076:binary_search(A, n, T) 975:{\displaystyle A_{m}=T} 11767:Condensed web version 11646:Fundamental algorithms 11091:, §4.4 ("Principles"). 10545:Pelc, Andrzej (2002). 10472:Pelc, Andrzej (1989). 9808:10.1006/jcss.2002.1822 9190: 9163: 9102: 9051: 9009: 8951: 8950:{\displaystyle I=E-2n} 8916: 8896: 8876: 8847: 8822: 8785: 8752: 8713: 8620: 8596: 8533:WikiJournal of Science 8502:WikiJournal of Science 8461:binary_search_by_key() 8422:CFArrayBSearchValues() 8206: 8184: 8160: 8118: 8096: 8075: 8055: 8035: 8009: 7950: 7929:computational geometry 7837: 7800: 7738: 7718: 7640: 7603: 7542: 7518: 7412: 7316: 7297: 7249:computational geometry 7238: 7197: 7177: 7142: 7109: 7068: 7048: 7028: 6955: 6935: 6909: 6884: 6854: 6834: 6795: 6752: 6698: 6677: 6615: 6586: 6547: 6454: 6420: 6397: 6334: 6333:{\textstyle O(\log n)} 6294: 6205: 6185: 6126: 5864: 5836:into the equation for 5830: 5799: 5507: 5478: 5455: 5432: 5406: 5386: 5360: 5294: 5265: 5221: 5199: 4905: 4882:into the equation for 4876: 4845: 4692: 4648:can be simplified to: 4642: 4613: 4562: 4471: 4433: 4396: 4346: 4323: 4264: 4235: 4211: 4185: 4153: 4127: 4100:model of computation. 4090: 4042: 3927: 3882: 3733: 3688: 3637: 3614: 3559: 3558:{\textstyle \log _{2}} 3528: 3502: 3450: 3442: 3435: 3415: 3329: 3302: 3274: 3248: 3203: 3196: 3134: 3113: 3086: 3065: 3045: 3012: 2973: 2972:{\displaystyle R>0} 2943: 2912: 2885: 2864: 2828: 2808: 2788: 2752: 2717: 2678: 2655: 2654:{\displaystyle L<R} 2626: 2606: 2586: 2566: 2505: 2485: 2461: 2441: 2421: 2401: 2374: 2341: 2340:{\displaystyle L<n} 2311: 2286: 2265: 2244: 2208: 2182: 2162: 2126: 2091: 2052: 2029: 2028:{\displaystyle L<R} 2000: 1980: 1960: 1940: 1907: 1839: 1819: 1690: 1670: 1637: 1606: 1586: 1566: 1530: 1504: 1484: 1448: 1413: 1374: 1351: 1322: 1296: 1276: 1256: 1226: 1200: 1180: 1152: 1070: 1040: 1020: 996: 976: 940: 914: 894: 858: 832: 812: 776: 741: 702: 679: 678:{\displaystyle L>R} 650: 624: 604: 584: 560: 540: 516: 496: 418: 337: 317: 272:computational geometry 245: 225: 188:Binary search runs in 11672:Sorting and searching 11575:Ruby pocket reference 11542:Leiserson, Charles E. 11356:Mac Developer Library 11323:Mac Developer Library 10732:10.1145/237814.237866 10531:10.1145/800133.804351 10285:10.1145/380752.380818 10239:10.1145/359545.359557 10128:10.1145/362686.362692 9693:10.1145/289251.289255 9680:ACM SIGNUM Newsletter 9468:10.1145/321119.321120 9393:10.1145/362663.362752 9279:10.1145/503561.503582 9191: 9164: 9103: 9052: 9010: 8952: 8917: 8897: 8877: 8848: 8823: 8786: 8753: 8714: 8621: 8619:{\displaystyle \log } 8597: 8546:10.15347/WJS/2019.005 8207: 8185: 8161: 8119: 8097: 8076: 8056: 8036: 8010: 7938: 7935:Implementation issues 7909:uniform binary search 7889:Moore School Lectures 7868:lexicographical order 7838: 7801: 7739: 7719: 7641: 7604: 7560:Quantum binary search 7543: 7541:{\displaystyle \tau } 7519: 7413: 7314: 7298: 7239: 7198: 7178: 7136: 7110: 7069: 7049: 7029: 6956: 6936: 6910: 6877: 6855: 6835: 6796: 6749:exponential searching 6746: 6699: 6674:Uniform binary search 6672: 6665:Uniform binary search 6659:Uniform binary search 6629:Other data structures 6616: 6587: 6548: 6455: 6415: 6398: 6335: 6295: 6249:locality of reference 6206: 6186: 6127: 5865: 5863:{\displaystyle T'(n)} 5831: 5800: 5508: 5479: 5456: 5433: 5407: 5387: 5361: 5295: 5266: 5231:Unsuccessful searches 5222: 5200: 4906: 4877: 4846: 4672: 4643: 4614: 4563: 4451: 4434: 4376: 4347: 4324: 4265: 4236: 4212: 4186: 4154: 4128: 4091: 4043: 3928: 3883: 3734: 3689: 3638: 3615: 3560: 3534:notation denotes the 3529: 3503: 3448: 3436: 3416: 3354: 3330: 3303: 3275: 3249: 3197: 3181: 3135: 3114: 3093:is not in the array, 3087: 3066: 3046: 3013: 2974: 2944: 2913: 2886: 2865: 2829: 2809: 2789: 2753: 2718: 2679: 2656: 2627: 2607: 2587: 2567: 2506: 2486: 2462: 2447:is not in the array, 2442: 2422: 2402: 2400:{\displaystyle A_{L}} 2375: 2342: 2312: 2287: 2266: 2245: 2209: 2183: 2163: 2127: 2092: 2053: 2030: 2001: 1981: 1961: 1941: 1908: 1840: 1820: 1691: 1671: 1638: 1607: 1587: 1567: 1531: 1505: 1485: 1449: 1414: 1375: 1352: 1323: 1297: 1277: 1257: 1227: 1201: 1181: 1162:Alternative procedure 1153: 1068: 1041: 1021: 997: 977: 941: 915: 895: 859: 833: 813: 777: 742: 703: 680: 651: 625: 605: 585: 561: 541: 517: 497: 419: 338: 318: 246: 226: 11974:Breadth-first search 11003:Google Research Blog 10442:10.1109/FOCS.2008.58 10436:. pp. 221–230. 10393:. pp. 519–532. 9715:Khuong, Paul-Virak; 9189:{\textstyle n>44} 9174: 9116: 9077: 9019: 8977: 8926: 8906: 8886: 8866: 8837: 8799: 8793:internal path length 8775: 8723: 8634: 8610: 8586: 8506:academic peer review 8491:Notes and references 8196: 8174: 8129: 8108: 8086: 8065: 8045: 8019: 8015:, then the value of 7984: 7925:fractional cascading 7897:Derrick Henry Lehmer 7814: 7752: 7728: 7658: 7617: 7568: 7532: 7422: 7324: 7272: 7207: 7187: 7149: 7139:fractional cascading 7129:Fractional cascading 7123:Fractional cascading 7078: 7058: 7038: 6965: 6945: 6919: 6899: 6893:linear interpolation 6880:interpolation search 6870:Interpolation search 6864:Interpolation search 6844: 6805: 6760: 6688: 6596: 6576: 6528: 6444: 6369: 6309: 6275: 6195: 6144: 5876: 5840: 5829:{\displaystyle E(n)} 5811: 5519: 5506:{\displaystyle I(n)} 5488: 5465: 5445: 5416: 5396: 5370: 5304: 5293:{\displaystyle E(n)} 5275: 5255: 5249:external path length 5241:extended binary tree 5211: 4917: 4904:{\displaystyle T(n)} 4886: 4875:{\displaystyle I(n)} 4857: 4654: 4641:{\displaystyle I(n)} 4623: 4574: 4448: 4358: 4336: 4274: 4263:{\displaystyle I(n)} 4245: 4225: 4219:internal path length 4195: 4175: 4137: 4117: 4089:{\displaystyle O(1)} 4071: 3937: 3892: 3746: 3698: 3647: 3627: 3573: 3542: 3512: 3461: 3425: 3363: 3313: 3292: 3258: 3238: 3186: 3124: 3097: 3076: 3055: 3022: 2983: 2957: 2927: 2896: 2875: 2841: 2818: 2798: 2765: 2727: 2692: 2668: 2639: 2616: 2596: 2576: 2556: 2495: 2475: 2451: 2431: 2411: 2384: 2351: 2325: 2301: 2276: 2255: 2221: 2192: 2172: 2139: 2101: 2066: 2042: 2013: 1990: 1970: 1950: 1930: 1849: 1829: 1761: 1680: 1647: 1621: 1596: 1576: 1543: 1514: 1494: 1461: 1423: 1388: 1364: 1335: 1306: 1286: 1266: 1246: 1210: 1190: 1170: 1127: 1030: 1010: 986: 953: 924: 904: 871: 842: 822: 789: 751: 716: 692: 663: 634: 614: 594: 574: 550: 530: 506: 428: 350: 327: 307: 268:fractional cascading 235: 200: 167:half-interval search 12064:Topological sorting 11994:Dynamic programming 11439:The Rust Foundation 10981:10.1145/52965.53012 10907:Guibas, Leonidas J. 10846:Guibas, Leonidas J. 10784:8 June 2016 at the 10676:2007PhRvA..75c2335C 10514:Kleitman, Daniel J. 10046:Judy IV shop manual 10043:Silverstein, Alan, 9932:, §6.4 ("Hashing"). 9561:, pp. 461–463. 8034:{\displaystyle L+R} 7978:arithmetic overflow 7913:Stanford University 7307:Noisy binary search 7034:of the way between 6934:{\displaystyle L,R} 6636:van Emde Boas trees 6417:Binary search trees 6365:, require at least 5431:{\displaystyle n+1} 5385:{\displaystyle n+1} 4210:{\displaystyle l+1} 4163:Successful searches 4152:{\displaystyle n+1} 3328:{\displaystyle r+1} 3273:{\displaystyle r-1} 3174:Approximate matches 3112:{\displaystyle n-R} 2942:{\displaystyle R-1} 2911:{\displaystyle m+1} 2207:{\displaystyle m+1} 1825:and the target was 1636:{\displaystyle L=R} 1529:{\displaystyle m-1} 1321:{\displaystyle n-1} 1236:Hermann Bottenbruch 1225:{\displaystyle L=R} 939:{\displaystyle m-1} 857:{\displaystyle m+1} 649:{\displaystyle n-1} 502:, and target value 231:comparisons, where 32: 12082:List of algorithms 11989:Divide and conquer 11984:Depth-first search 11979:Brute-force search 11893:Binary search tree 11788:Stroustrup, Bjarne 11470:Programming pearls 11263:Oracle Corporation 11229:Oracle Corporation 11221:"java.util.Arrays" 10965:Pattis, Richard E. 10932:10.1007/BF01840441 10881:10.1007/BF01840440 10762:10.1147/rd.12.0130 10056:, pp. 80–81, 9454:Journal of the ACM 9346:Weisstein, Eric W. 9332:Cormen et al. 2009 9186: 9159: 9098: 9047: 9005: 8947: 8912: 8902:. For any tree of 8892: 8872: 8843: 8818: 8781: 8748: 8709: 8616: 8592: 8457:binary_search_by() 8386:2.0 offers static 8223:standard libraries 8202: 8180: 8156: 8114: 8092: 8071: 8051: 8031: 8005: 7963:Programming Pearls 7921:Leonidas J. Guibas 7915:in 1971. In 1986, 7862:numbers and their 7833: 7808:Grover's algorithm 7796: 7734: 7714: 7636: 7611:Quantum algorithms 7599: 7538: 7514: 7408: 7317: 7293: 7234: 7193: 7173: 7143: 7105: 7064: 7044: 7024: 6951: 6931: 6905: 6885: 6850: 6830: 6791: 6753: 6739:Exponential search 6733:Exponential search 6694: 6678: 6611: 6582: 6543: 6485:associative arrays 6450: 6425:binary search tree 6421: 6393: 6355:sorting algorithms 6330: 6290: 6201: 6181: 6122: 5860: 5826: 5795: 5503: 5477:{\displaystyle 2n} 5474: 5451: 5428: 5412:because there are 5402: 5382: 5356: 5290: 5261: 5217: 5195: 4901: 4872: 4841: 4638: 4609: 4558: 4429: 4342: 4319: 4260: 4231: 4207: 4181: 4149: 4123: 4086: 4038: 3923: 3878: 3729: 3684: 3633: 3610: 3555: 3524: 3498: 3451: 3443: 3434:{\displaystyle 40} 3431: 3411: 3325: 3298: 3270: 3244: 3204: 3192: 3130: 3109: 3082: 3061: 3041: 3008: 2969: 2939: 2908: 2881: 2860: 2824: 2804: 2784: 2748: 2713: 2674: 2651: 2622: 2602: 2582: 2562: 2501: 2481: 2457: 2437: 2417: 2397: 2370: 2337: 2307: 2282: 2261: 2240: 2204: 2178: 2158: 2122: 2087: 2048: 2025: 1996: 1976: 1956: 1936: 1903: 1835: 1815: 1753:Duplicate elements 1686: 1666: 1633: 1602: 1582: 1562: 1526: 1500: 1480: 1444: 1409: 1370: 1347: 1318: 1292: 1272: 1252: 1222: 1196: 1176: 1148: 1071: 1036: 1016: 992: 972: 936: 910: 890: 854: 828: 808: 772: 737: 698: 675: 646: 620: 600: 580: 556: 536: 512: 492: 414: 333: 313: 280:binary search tree 276:Exponential search 241: 221: 171:logarithmic search 30: 12123:Search algorithms 12090: 12089: 11888:Associative array 11801:978-0-321-56384-2 11762:978-0-321-57351-3 11747:Sedgewick, Robert 11738:978-0-7923-7668-2 11711:978-0-201-03804-0 11685:978-0-201-89685-5 11659:978-0-201-89683-1 11633:978-1-86094-635-6 11614:978-1-58488-455-2 11597:Goldman, Sally A. 11588:978-1-4919-2601-7 11565:978-0-262-03384-8 11546:Rivest, Ronald L. 11538:Cormen, Thomas H. 11529:978-981-238-348-8 11506:978-0-19-968897-5 11483:978-0-201-65788-3 10903:Chazelle, Bernard 10842:Chazelle, Bernard 10817:10.1090/psapm/010 10654:Physical Review A 10506:Rivest, Ronald L. 10451:978-0-7695-3436-7 10316:Chazelle, Bernard 10294:978-1-58113-349-3 10267:Chazelle, Bernard 9964:Tarjan, Robert E. 9157: 9143: 8915:{\displaystyle n} 8895:{\displaystyle E} 8875:{\displaystyle I} 8846:{\displaystyle I} 8816: 8784:{\displaystyle I} 8595:{\displaystyle O} 8465:partition_point() 8205:{\displaystyle R} 8183:{\displaystyle L} 8154: 8117:{\displaystyle R} 8095:{\displaystyle L} 8074:{\displaystyle R} 8054:{\displaystyle L} 8003: 7828: 7746:natural logarithm 7737:{\textstyle \ln } 7669: 7648:quantum computers 7406: 7382: 7257:Internet Protocol 7067:{\displaystyle R} 7047:{\displaystyle L} 6954:{\displaystyle T} 6908:{\displaystyle A} 6878:Visualization of 6747:Visualization of 6727:decimal computers 6697:{\displaystyle m} 6614:{\textstyle O(k)} 6546:{\textstyle O(1)} 6483:For implementing 6293:{\textstyle O(n)} 6019: 5454:{\displaystyle n} 5405:{\displaystyle n} 5354: 5264:{\displaystyle n} 5239:, which forms an 5220:{\displaystyle n} 5061: 4607: 4591: 4345:{\displaystyle n} 4317: 4234:{\displaystyle n} 4184:{\displaystyle l} 4126:{\displaystyle n} 3301:{\displaystyle r} 3247:{\displaystyle r} 3195:{\displaystyle 5} 3133:{\displaystyle T} 3085:{\displaystyle T} 3064:{\displaystyle T} 2884:{\displaystyle L} 2827:{\displaystyle m} 2807:{\displaystyle R} 2746: 2711: 2677:{\displaystyle m} 2625:{\displaystyle n} 2605:{\displaystyle R} 2585:{\displaystyle 0} 2565:{\displaystyle L} 2504:{\displaystyle T} 2484:{\displaystyle T} 2460:{\displaystyle L} 2440:{\displaystyle T} 2420:{\displaystyle T} 2310:{\displaystyle L} 2285:{\displaystyle m} 2264:{\displaystyle R} 2181:{\displaystyle L} 2120: 2085: 2051:{\displaystyle m} 1999:{\displaystyle n} 1979:{\displaystyle R} 1959:{\displaystyle 0} 1939:{\displaystyle L} 1838:{\displaystyle 4} 1689:{\displaystyle L} 1605:{\displaystyle m} 1585:{\displaystyle L} 1503:{\displaystyle R} 1442: 1407: 1373:{\displaystyle m} 1295:{\displaystyle R} 1275:{\displaystyle 0} 1255:{\displaystyle L} 1199:{\displaystyle T} 1179:{\displaystyle m} 1146: 1039:{\displaystyle R} 1019:{\displaystyle L} 995:{\displaystyle m} 946:and go to step 2. 913:{\displaystyle R} 864:and go to step 2. 831:{\displaystyle L} 770: 735: 701:{\displaystyle m} 623:{\displaystyle R} 603:{\displaystyle 0} 583:{\displaystyle L} 559:{\displaystyle A} 539:{\displaystyle T} 515:{\displaystyle T} 424:sorted such that 336:{\displaystyle n} 316:{\displaystyle A} 244:{\displaystyle n} 155: 154: 12135: 12059:String-searching 11858: 11851: 11844: 11835: 11834: 11805: 11782: 11781: 11774: 11773: 11766: 11742: 11715: 11689: 11663: 11637: 11618: 11592: 11569: 11533: 11520:World Scientific 11510: 11487: 11472:(2nd ed.). 11451: 11450: 11448: 11446: 11430: 11427:"Primitive Type 11423: 11417: 11411: 11405: 11404: 11402: 11400: 11381: 11375: 11374: 11372: 11370: 11348: 11342: 11341: 11339: 11337: 11315: 11309: 11308: 11306: 11304: 11285: 11279: 11278: 11276: 11274: 11251: 11245: 11244: 11242: 11240: 11217: 11211: 11210: 11208: 11206: 11187: 11181: 11180: 11169: 11163: 11162: 11160: 11158: 11144: 11138: 11132: 11126: 11125: 11123: 11121: 11108:(7th ed.). 11098: 11092: 11086: 11080: 11079: 11077: 11075: 11069: 11054: 11034: 11025: 11019: 11018: 11016: 11014: 10991: 10985: 10984: 10961: 10955: 10949: 10943: 10942: 10926:(1–4): 163–191, 10915: 10899: 10893: 10892: 10874: 10865:(1–4): 133–162. 10854: 10838: 10832: 10831: 10819: 10795: 10789: 10772: 10766: 10765: 10742: 10736: 10735: 10725: 10723:quant-ph/9605043 10702: 10696: 10695: 10669: 10667:quant-ph/0608161 10649: 10643: 10642: 10624: 10622:quant-ph/0102078 10602: 10596: 10595: 10582:(in Hungarian). 10575: 10569: 10568: 10566: 10542: 10536: 10535: 10533: 10516:; Winklmann, K. 10510:Meyer, Albert R. 10502: 10496: 10495: 10493: 10469: 10463: 10462: 10460: 10428: 10419: 10413: 10412: 10402: 10382: 10376: 10375: 10373: 10371: 10365: 10342: 10324: 10312: 10306: 10305: 10303: 10301: 10263: 10252: 10251: 10241: 10211: 10205: 10199: 10193: 10187: 10176: 10170: 10164: 10158: 10152: 10146: 10140: 10139: 10121: 10099: 10093: 10092: 10090: 10074: 10065: 10064: 10062: 10051: 10040: 10031: 10025: 10019: 10018: 10016: 10014: 10008: 10001: 9992: 9986: 9985: 9951: 9945: 9939: 9933: 9927: 9921: 9915: 9909: 9903: 9897: 9891: 9885: 9879: 9873: 9867: 9861: 9855: 9849: 9843: 9837: 9831: 9825: 9819: 9813: 9812: 9810: 9780: 9767: 9761: 9755: 9754: 9736: 9712: 9706: 9705: 9695: 9671: 9665: 9659: 9650: 9644: 9633: 9627: 9621: 9615: 9609: 9603: 9574: 9568: 9562: 9556: 9545: 9539: 9528: 9522: 9513: 9507: 9490: 9488: 9470: 9444: 9431: 9425: 9414: 9413: 9395: 9369: 9360: 9359: 9358: 9341: 9335: 9329: 9323: 9317: 9311: 9305: 9296: 9295: 9293: 9291: 9281: 9263: 9246: 9243: 9237: 9230: 9224: 9221: 9215: 9212: 9206: 9203: 9197: 9195: 9193: 9192: 9187: 9168: 9166: 9165: 9160: 9158: 9156: 9148: 9144: 9141: 9135: 9107: 9105: 9104: 9099: 9064: 9058: 9056: 9054: 9053: 9048: 9034: 9033: 9014: 9012: 9011: 9006: 8992: 8991: 8964: 8958: 8956: 8954: 8953: 8948: 8921: 8919: 8918: 8913: 8901: 8899: 8898: 8893: 8881: 8879: 8878: 8873: 8857:proved that the 8852: 8850: 8849: 8844: 8827: 8825: 8824: 8819: 8817: 8809: 8790: 8788: 8787: 8782: 8765: 8759: 8757: 8755: 8754: 8749: 8735: 8734: 8718: 8716: 8715: 8710: 8696: 8695: 8671: 8670: 8646: 8645: 8625: 8623: 8622: 8617: 8601: 8599: 8598: 8593: 8580: 8566: 8548: 8530: 8521: 8510:reviewer reports 8499: 8478:Bisection method 8466: 8462: 8458: 8454: 8444: 8434: 8424: 8414: 8397: 8393: 8376:s, respectively. 8375: 8371: 8368:in the standard 8367: 8361: 8355: 8349:offers a set of 8342: 8338: 8334: 8330: 8326: 8316: 8306: 8302: 8298: 8294: 8290: 8286: 8282: 8278: 8268: 8264: 8260: 8256: 8251:standard library 8241:standard library 8238: 8221:Many languages' 8211: 8209: 8208: 8203: 8189: 8187: 8186: 8181: 8165: 8163: 8162: 8157: 8155: 8150: 8139: 8123: 8121: 8120: 8115: 8101: 8099: 8098: 8093: 8080: 8078: 8077: 8072: 8060: 8058: 8057: 8052: 8040: 8038: 8037: 8032: 8014: 8012: 8011: 8006: 8004: 7999: 7988: 7948: 7917:Bernard Chazelle 7857: 7854: 7842: 7840: 7839: 7834: 7829: 7824: 7805: 7803: 7802: 7797: 7789: 7788: 7767: 7766: 7743: 7741: 7740: 7735: 7723: 7721: 7720: 7715: 7707: 7706: 7670: 7662: 7645: 7643: 7642: 7637: 7629: 7628: 7608: 7606: 7605: 7600: 7583: 7582: 7554:Twenty Questions 7547: 7545: 7544: 7539: 7523: 7521: 7520: 7515: 7495: 7494: 7455: 7454: 7417: 7415: 7414: 7409: 7407: 7405: 7388: 7383: 7381: 7367: 7354: 7353: 7343: 7302: 7300: 7299: 7294: 7243: 7241: 7240: 7235: 7202: 7200: 7199: 7194: 7182: 7180: 7179: 7174: 7114: 7112: 7111: 7106: 7073: 7071: 7070: 7065: 7053: 7051: 7050: 7045: 7033: 7031: 7030: 7025: 7020: 7019: 7007: 7006: 6994: 6986: 6985: 6960: 6958: 6957: 6952: 6940: 6938: 6937: 6932: 6914: 6912: 6911: 6906: 6859: 6857: 6856: 6851: 6839: 6837: 6836: 6831: 6820: 6819: 6800: 6798: 6797: 6792: 6775: 6774: 6723: 6719: 6715: 6711: 6707: 6703: 6701: 6700: 6695: 6620: 6618: 6617: 6612: 6591: 6589: 6588: 6583: 6552: 6550: 6549: 6544: 6459: 6457: 6456: 6451: 6402: 6400: 6399: 6394: 6339: 6337: 6336: 6331: 6299: 6297: 6296: 6291: 6210: 6208: 6207: 6202: 6190: 6188: 6187: 6182: 6159: 6158: 6131: 6129: 6128: 6123: 6106: 6101: 6100: 6078: 6077: 6036: 6035: 6020: 6018: 6001: 6000: 5999: 5977: 5976: 5932: 5931: 5900: 5886: 5869: 5867: 5866: 5861: 5850: 5835: 5833: 5832: 5827: 5804: 5802: 5801: 5796: 5794: 5793: 5771: 5770: 5726: 5725: 5683: 5679: 5672: 5671: 5664: 5660: 5641: 5640: 5618: 5614: 5595: 5594: 5512: 5510: 5509: 5504: 5483: 5481: 5480: 5475: 5460: 5458: 5457: 5452: 5437: 5435: 5434: 5429: 5411: 5409: 5408: 5403: 5391: 5389: 5388: 5383: 5365: 5363: 5362: 5357: 5355: 5353: 5342: 5328: 5314: 5299: 5297: 5296: 5291: 5270: 5268: 5267: 5262: 5226: 5224: 5223: 5218: 5204: 5202: 5201: 5196: 5191: 5162: 5161: 5146: 5145: 5123: 5122: 5078: 5077: 5062: 5057: 5050: 5049: 5042: 5038: 5019: 5018: 4996: 4992: 4973: 4972: 4942: 4910: 4908: 4907: 4902: 4881: 4879: 4878: 4873: 4850: 4848: 4847: 4842: 4834: 4833: 4826: 4822: 4803: 4802: 4780: 4776: 4757: 4756: 4724: 4720: 4707: 4706: 4691: 4686: 4647: 4645: 4644: 4639: 4618: 4616: 4615: 4610: 4608: 4600: 4592: 4584: 4567: 4565: 4564: 4559: 4503: 4499: 4486: 4485: 4470: 4465: 4438: 4436: 4435: 4430: 4428: 4424: 4411: 4410: 4395: 4390: 4351: 4349: 4348: 4343: 4328: 4326: 4325: 4320: 4318: 4313: 4299: 4269: 4267: 4266: 4261: 4240: 4238: 4237: 4232: 4216: 4214: 4213: 4208: 4190: 4188: 4187: 4182: 4158: 4156: 4155: 4150: 4132: 4130: 4129: 4124: 4095: 4093: 4092: 4087: 4063:Space complexity 4047: 4045: 4044: 4039: 4022: 4017: 4016: 3994: 3993: 3952: 3951: 3932: 3930: 3929: 3924: 3904: 3903: 3887: 3885: 3884: 3879: 3874: 3845: 3844: 3829: 3828: 3806: 3805: 3761: 3760: 3738: 3736: 3735: 3730: 3713: 3712: 3693: 3691: 3690: 3685: 3662: 3661: 3642: 3640: 3639: 3634: 3619: 3617: 3616: 3611: 3588: 3587: 3567:binary logarithm 3564: 3562: 3561: 3556: 3554: 3553: 3533: 3531: 3530: 3525: 3507: 3505: 3504: 3499: 3476: 3475: 3440: 3438: 3437: 3432: 3420: 3418: 3417: 3414:{\displaystyle } 3412: 3334: 3332: 3331: 3326: 3307: 3305: 3304: 3299: 3279: 3277: 3276: 3271: 3253: 3251: 3250: 3245: 3213:nearest neighbor 3201: 3199: 3198: 3193: 3147: 3139: 3137: 3136: 3131: 3118: 3116: 3115: 3110: 3091: 3089: 3088: 3083: 3070: 3068: 3067: 3062: 3050: 3048: 3047: 3042: 3040: 3039: 3017: 3015: 3014: 3009: 3001: 3000: 2978: 2976: 2975: 2970: 2948: 2946: 2945: 2940: 2917: 2915: 2914: 2909: 2890: 2888: 2887: 2882: 2869: 2867: 2866: 2861: 2853: 2852: 2833: 2831: 2830: 2825: 2813: 2811: 2810: 2805: 2793: 2791: 2790: 2785: 2777: 2776: 2757: 2755: 2754: 2749: 2747: 2742: 2731: 2722: 2720: 2719: 2714: 2712: 2707: 2696: 2683: 2681: 2680: 2675: 2660: 2658: 2657: 2652: 2631: 2629: 2628: 2623: 2611: 2609: 2608: 2603: 2591: 2589: 2588: 2583: 2571: 2569: 2568: 2563: 2517: 2510: 2508: 2507: 2502: 2490: 2488: 2487: 2482: 2466: 2464: 2463: 2458: 2446: 2444: 2443: 2438: 2426: 2424: 2423: 2418: 2406: 2404: 2403: 2398: 2396: 2395: 2379: 2377: 2376: 2371: 2363: 2362: 2346: 2344: 2343: 2338: 2316: 2314: 2313: 2308: 2291: 2289: 2288: 2283: 2270: 2268: 2267: 2262: 2249: 2247: 2246: 2241: 2233: 2232: 2213: 2211: 2210: 2205: 2187: 2185: 2184: 2179: 2167: 2165: 2164: 2159: 2151: 2150: 2131: 2129: 2128: 2123: 2121: 2116: 2105: 2096: 2094: 2093: 2088: 2086: 2081: 2070: 2057: 2055: 2054: 2049: 2034: 2032: 2031: 2026: 2005: 2003: 2002: 1997: 1985: 1983: 1982: 1977: 1965: 1963: 1962: 1957: 1945: 1943: 1942: 1937: 1912: 1910: 1909: 1906:{\displaystyle } 1904: 1844: 1842: 1841: 1836: 1824: 1822: 1821: 1818:{\displaystyle } 1816: 1703: 1695: 1693: 1692: 1687: 1675: 1673: 1672: 1667: 1659: 1658: 1642: 1640: 1639: 1634: 1611: 1609: 1608: 1603: 1591: 1589: 1588: 1583: 1571: 1569: 1568: 1563: 1555: 1554: 1535: 1533: 1532: 1527: 1509: 1507: 1506: 1501: 1489: 1487: 1486: 1481: 1473: 1472: 1453: 1451: 1450: 1445: 1443: 1438: 1427: 1418: 1416: 1415: 1410: 1408: 1403: 1392: 1379: 1377: 1376: 1371: 1356: 1354: 1353: 1348: 1327: 1325: 1324: 1319: 1301: 1299: 1298: 1293: 1281: 1279: 1278: 1273: 1261: 1259: 1258: 1253: 1231: 1229: 1228: 1223: 1205: 1203: 1202: 1197: 1185: 1183: 1182: 1177: 1157: 1155: 1154: 1149: 1147: 1142: 1131: 1061: 1053: 1045: 1043: 1042: 1037: 1025: 1023: 1022: 1017: 1001: 999: 998: 993: 981: 979: 978: 973: 965: 964: 945: 943: 942: 937: 919: 917: 916: 911: 899: 897: 896: 891: 883: 882: 863: 861: 860: 855: 837: 835: 834: 829: 817: 815: 814: 809: 801: 800: 781: 779: 778: 773: 771: 766: 755: 746: 744: 743: 738: 736: 731: 720: 707: 705: 704: 699: 684: 682: 681: 676: 655: 653: 652: 647: 629: 627: 626: 621: 609: 607: 606: 601: 589: 587: 586: 581: 565: 563: 562: 557: 545: 543: 542: 537: 522:, the following 521: 519: 518: 513: 501: 499: 498: 493: 491: 490: 466: 465: 453: 452: 440: 439: 423: 421: 420: 415: 413: 412: 388: 387: 375: 374: 362: 361: 342: 340: 339: 334: 322: 320: 319: 314: 250: 248: 247: 242: 230: 228: 227: 222: 190:logarithmic time 179:search algorithm 165:, also known as 159:computer science 134:space complexity 52:Search algorithm 40: 33: 29: 21:bisection method 12143: 12142: 12138: 12137: 12136: 12134: 12133: 12132: 12093: 12092: 12091: 12086: 12068: 11999:Graph traversal 11952: 11876:Data structures 11871: 11865:Data structures 11862: 11829:Wayback Machine 11813: 11808: 11802: 11776: 11775:; book version 11768: 11763: 11739: 11712: 11686: 11660: 11634: 11615: 11589: 11566: 11550:Stein, Clifford 11530: 11507: 11484: 11460: 11455: 11454: 11444: 11442: 11428: 11425: 11424: 11420: 11414:Fitzgerald 2015 11412: 11408: 11398: 11396: 11383: 11382: 11378: 11368: 11366: 11350: 11349: 11345: 11335: 11333: 11317: 11316: 11312: 11302: 11300: 11287: 11286: 11282: 11272: 11270: 11253: 11252: 11248: 11238: 11236: 11219: 11218: 11214: 11204: 11202: 11189: 11188: 11184: 11170: 11166: 11156: 11154: 11146: 11145: 11141: 11135:Stroustrup 2013 11133: 11129: 11119: 11117: 11100: 11099: 11095: 11087: 11083: 11073: 11071: 11067: 11032: 11026: 11022: 11012: 11010: 10997:(2 June 2006). 10992: 10988: 10969:SIGCSE Bulletin 10962: 10958: 10950: 10946: 10913: 10900: 10896: 10872:10.1.1.117.8349 10852: 10839: 10835: 10828: 10796: 10792: 10786:Wayback Machine 10773: 10769: 10743: 10739: 10703: 10699: 10650: 10646: 10603: 10599: 10576: 10572: 10557:(1–2): 71–109. 10543: 10539: 10503: 10499: 10470: 10466: 10458: 10452: 10426: 10420: 10416: 10383: 10379: 10369: 10367: 10363: 10340:10.1.1.298.7772 10322: 10313: 10309: 10299: 10297: 10295: 10264: 10255: 10212: 10208: 10200: 10196: 10188: 10179: 10171: 10167: 10159: 10155: 10147: 10143: 10119:10.1.1.641.9096 10100: 10096: 10075: 10068: 10060: 10054:Hewlett-Packard 10049: 10041: 10034: 10026: 10022: 10012: 10010: 10006: 9999: 9993: 9989: 9952: 9948: 9940: 9936: 9928: 9924: 9916: 9912: 9904: 9900: 9892: 9888: 9880: 9876: 9868: 9864: 9856: 9852: 9844: 9840: 9832: 9828: 9820: 9816: 9781: 9770: 9762: 9758: 9743:10.1145/3053370 9727:. Article 1.3. 9713: 9709: 9672: 9668: 9660: 9653: 9645: 9636: 9628: 9624: 9616: 9612: 9604: 9577: 9569: 9565: 9557: 9548: 9540: 9531: 9527:, pp. 8–9. 9523: 9516: 9508: 9493: 9445: 9434: 9426: 9417: 9370: 9363: 9349:"Binary search" 9342: 9338: 9330: 9326: 9318: 9314: 9306: 9299: 9289: 9287: 9264: 9260: 9255: 9250: 9249: 9244: 9240: 9231: 9227: 9222: 9218: 9213: 9209: 9204: 9200: 9175: 9172: 9171: 9149: 9142: mod 9140: 9136: 9134: 9117: 9114: 9113: 9078: 9075: 9074: 9065: 9061: 9029: 9025: 9020: 9017: 9016: 8987: 8983: 8978: 8975: 8974: 8965: 8961: 8927: 8924: 8923: 8907: 8904: 8903: 8887: 8884: 8883: 8867: 8864: 8863: 8838: 8835: 8834: 8808: 8800: 8797: 8796: 8776: 8773: 8772: 8766: 8762: 8730: 8726: 8724: 8721: 8720: 8691: 8687: 8666: 8662: 8641: 8637: 8635: 8632: 8631: 8611: 8608: 8607: 8587: 8584: 8583: 8581: 8577: 8572: 8528: 8523: 8517: 8493: 8474: 8464: 8460: 8456: 8453:binary_search() 8452: 8442: 8432: 8420: 8417:Core Foundation 8410: 8395: 8391: 8373: 8369: 8363: 8357: 8353: 8340: 8336: 8332: 8328: 8324: 8314: 8304: 8300: 8296: 8292: 8288: 8284: 8280: 8276: 8266: 8262: 8258: 8255:binary_search() 8254: 8236: 8219: 8217:Library support 8197: 8194: 8193: 8175: 8172: 8171: 8140: 8138: 8130: 8127: 8126: 8109: 8106: 8105: 8087: 8084: 8083: 8066: 8063: 8062: 8046: 8043: 8042: 8020: 8017: 8016: 7989: 7987: 7985: 7982: 7981: 7965:, contained an 7949: 7944: 7937: 7855: 7849: 7823: 7815: 7812: 7811: 7784: 7780: 7762: 7758: 7753: 7750: 7749: 7729: 7726: 7725: 7702: 7698: 7661: 7659: 7656: 7655: 7624: 7620: 7618: 7615: 7614: 7578: 7574: 7569: 7566: 7565: 7562: 7552:, a variant of 7550:Rényi-Ulam game 7533: 7530: 7529: 7490: 7486: 7450: 7446: 7423: 7420: 7419: 7392: 7387: 7368: 7349: 7345: 7344: 7342: 7325: 7322: 7321: 7309: 7273: 7270: 7269: 7265: 7208: 7205: 7204: 7188: 7185: 7184: 7150: 7147: 7146: 7131: 7125: 7079: 7076: 7075: 7059: 7056: 7055: 7039: 7036: 7035: 7015: 7011: 7002: 6998: 6990: 6981: 6977: 6966: 6963: 6962: 6946: 6943: 6942: 6920: 6917: 6916: 6900: 6897: 6896: 6872: 6866: 6845: 6842: 6841: 6815: 6811: 6806: 6803: 6802: 6770: 6766: 6761: 6758: 6757: 6741: 6735: 6721: 6717: 6713: 6709: 6705: 6689: 6686: 6685: 6667: 6661: 6656: 6631: 6623:false positives 6597: 6594: 6593: 6577: 6574: 6573: 6529: 6526: 6525: 6510: 6481: 6445: 6442: 6441: 6410: 6370: 6367: 6366: 6347: 6310: 6307: 6306: 6276: 6273: 6272: 6269: 6239:has a hardware 6217: 6196: 6193: 6192: 6154: 6150: 6145: 6142: 6141: 6137: 6102: 6073: 6069: 6065: 6061: 6031: 6027: 6002: 5972: 5968: 5964: 5960: 5927: 5923: 5901: 5899: 5879: 5877: 5874: 5873: 5843: 5841: 5838: 5837: 5812: 5809: 5808: 5766: 5762: 5758: 5754: 5721: 5717: 5636: 5632: 5631: 5627: 5626: 5622: 5590: 5586: 5585: 5581: 5565: 5561: 5520: 5517: 5516: 5489: 5486: 5485: 5466: 5463: 5462: 5446: 5443: 5442: 5417: 5414: 5413: 5397: 5394: 5393: 5371: 5368: 5367: 5343: 5329: 5327: 5307: 5305: 5302: 5301: 5276: 5273: 5272: 5256: 5253: 5252: 5233: 5212: 5209: 5208: 5187: 5157: 5153: 5118: 5114: 5110: 5106: 5073: 5069: 5014: 5010: 5009: 5005: 5004: 5000: 4968: 4964: 4963: 4959: 4943: 4941: 4918: 4915: 4914: 4887: 4884: 4883: 4858: 4855: 4854: 4798: 4794: 4793: 4789: 4788: 4784: 4752: 4748: 4747: 4743: 4702: 4698: 4697: 4693: 4687: 4676: 4655: 4652: 4651: 4624: 4621: 4620: 4599: 4583: 4575: 4572: 4571: 4481: 4477: 4476: 4472: 4466: 4455: 4449: 4446: 4445: 4406: 4402: 4401: 4397: 4391: 4380: 4359: 4356: 4355: 4337: 4334: 4333: 4300: 4298: 4275: 4272: 4271: 4246: 4243: 4242: 4226: 4223: 4222: 4196: 4193: 4192: 4176: 4173: 4172: 4165: 4138: 4135: 4134: 4118: 4115: 4114: 4106: 4072: 4069: 4068: 4065: 4018: 3989: 3985: 3981: 3977: 3947: 3943: 3938: 3935: 3934: 3899: 3895: 3893: 3890: 3889: 3870: 3840: 3836: 3801: 3797: 3793: 3789: 3756: 3752: 3747: 3744: 3743: 3708: 3704: 3699: 3696: 3695: 3657: 3653: 3648: 3645: 3644: 3628: 3625: 3624: 3583: 3579: 3574: 3571: 3570: 3549: 3545: 3543: 3540: 3539: 3513: 3510: 3509: 3471: 3467: 3462: 3459: 3458: 3426: 3423: 3422: 3364: 3361: 3360: 3349: 3314: 3311: 3310: 3293: 3290: 3289: 3259: 3256: 3255: 3239: 3236: 3235: 3187: 3184: 3183: 3176: 3171: 3145: 3125: 3122: 3121: 3098: 3095: 3094: 3077: 3074: 3073: 3056: 3053: 3052: 3029: 3025: 3023: 3020: 3019: 2990: 2986: 2984: 2981: 2980: 2958: 2955: 2954: 2928: 2925: 2924: 2897: 2894: 2893: 2876: 2873: 2872: 2848: 2844: 2842: 2839: 2838: 2819: 2816: 2815: 2799: 2796: 2795: 2772: 2768: 2766: 2763: 2762: 2732: 2730: 2728: 2725: 2724: 2697: 2695: 2693: 2690: 2689: 2669: 2666: 2665: 2640: 2637: 2636: 2617: 2614: 2613: 2597: 2594: 2593: 2577: 2574: 2573: 2557: 2554: 2553: 2546: 2541: 2515: 2496: 2493: 2492: 2476: 2473: 2472: 2452: 2449: 2448: 2432: 2429: 2428: 2412: 2409: 2408: 2391: 2387: 2385: 2382: 2381: 2358: 2354: 2352: 2349: 2348: 2326: 2323: 2322: 2302: 2299: 2298: 2277: 2274: 2273: 2256: 2253: 2252: 2228: 2224: 2222: 2219: 2218: 2193: 2190: 2189: 2173: 2170: 2169: 2146: 2142: 2140: 2137: 2136: 2106: 2104: 2102: 2099: 2098: 2071: 2069: 2067: 2064: 2063: 2043: 2040: 2039: 2014: 2011: 2010: 1991: 1988: 1987: 1971: 1968: 1967: 1951: 1948: 1947: 1931: 1928: 1927: 1920: 1850: 1847: 1846: 1830: 1827: 1826: 1762: 1759: 1758: 1755: 1750: 1701: 1681: 1678: 1677: 1654: 1650: 1648: 1645: 1644: 1622: 1619: 1618: 1597: 1594: 1593: 1577: 1574: 1573: 1550: 1546: 1544: 1541: 1540: 1515: 1512: 1511: 1495: 1492: 1491: 1468: 1464: 1462: 1459: 1458: 1428: 1426: 1424: 1421: 1420: 1393: 1391: 1389: 1386: 1385: 1365: 1362: 1361: 1336: 1333: 1332: 1307: 1304: 1303: 1287: 1284: 1283: 1267: 1264: 1263: 1247: 1244: 1243: 1211: 1208: 1207: 1191: 1188: 1187: 1171: 1168: 1167: 1164: 1132: 1130: 1128: 1125: 1124: 1117: 1059: 1051: 1031: 1028: 1027: 1011: 1008: 1007: 987: 984: 983: 960: 956: 954: 951: 950: 925: 922: 921: 905: 902: 901: 878: 874: 872: 869: 868: 843: 840: 839: 823: 820: 819: 796: 792: 790: 787: 786: 756: 754: 752: 749: 748: 721: 719: 717: 714: 713: 693: 690: 689: 664: 661: 660: 635: 632: 631: 615: 612: 611: 595: 592: 591: 575: 572: 571: 551: 548: 547: 531: 528: 527: 507: 504: 503: 480: 476: 461: 457: 448: 444: 435: 431: 429: 426: 425: 402: 398: 383: 379: 370: 366: 357: 353: 351: 348: 347: 328: 325: 324: 308: 305: 304: 303:Given an array 301: 292: 257:data structures 236: 233: 232: 201: 198: 197: 43: 24: 17: 12: 11: 5: 12141: 12131: 12130: 12125: 12120: 12115: 12110: 12105: 12088: 12087: 12085: 12084: 12079: 12073: 12070: 12069: 12067: 12066: 12061: 12056: 12051: 12046: 12041: 12036: 12031: 12026: 12021: 12016: 12011: 12006: 12001: 11996: 11991: 11986: 11981: 11976: 11971: 11966: 11960: 11958: 11954: 11953: 11951: 11950: 11945: 11940: 11935: 11930: 11925: 11920: 11915: 11910: 11905: 11900: 11895: 11890: 11885: 11879: 11877: 11873: 11872: 11861: 11860: 11853: 11846: 11838: 11832: 11831: 11819: 11812: 11811:External links 11809: 11807: 11806: 11800: 11784: 11761: 11743: 11737: 11716: 11710: 11690: 11684: 11664: 11658: 11638: 11632: 11619: 11613: 11593: 11587: 11579:O'Reilly Media 11570: 11564: 11534: 11528: 11511: 11505: 11488: 11482: 11474:Addison-Wesley 11461: 11459: 11456: 11453: 11452: 11418: 11416:, p. 152. 11406: 11376: 11343: 11310: 11280: 11246: 11212: 11191:"Package sort" 11182: 11164: 11139: 11137:, p. 945. 11127: 11110:The Open Group 11093: 11081: 11052:10.1.1.13.5631 11020: 10986: 10956: 10944: 10894: 10833: 10826: 10790: 10767: 10756:(2): 130–146. 10737: 10706:Grover, Lov K. 10697: 10644: 10615:(4): 429–448. 10597: 10570: 10537: 10497: 10484:(2): 185–202. 10464: 10450: 10414: 10377: 10333:(2): 269–284. 10307: 10293: 10253: 10232:(7): 550–553. 10206: 10194: 10177: 10165: 10153: 10141: 10112:(7): 422–426. 10094: 10066: 10032: 10020: 9987: 9976:(4): 738–761. 9960:Mehlhorn, Kurt 9946: 9934: 9922: 9910: 9898: 9886: 9874: 9862: 9850: 9838: 9826: 9814: 9785:Fich, Faith E. 9768: 9756: 9707: 9666: 9651: 9634: 9632:, p. 169. 9622: 9610: 9575: 9563: 9546: 9529: 9514: 9491: 9461:(2): 161–221. 9432: 9415: 9386:(9): 602–603. 9361: 9336: 9324: 9312: 9297: 9257: 9256: 9254: 9251: 9248: 9247: 9238: 9234:cuckoo hashing 9225: 9216: 9207: 9198: 9185: 9182: 9179: 9155: 9152: 9147: 9139: 9133: 9130: 9127: 9124: 9121: 9097: 9094: 9091: 9088: 9085: 9082: 9059: 9046: 9043: 9040: 9037: 9032: 9028: 9024: 9004: 9001: 8998: 8995: 8990: 8986: 8982: 8969:showed on his 8959: 8946: 8943: 8940: 8937: 8934: 8931: 8911: 8891: 8871: 8842: 8815: 8812: 8807: 8804: 8780: 8760: 8758:is a constant. 8747: 8744: 8741: 8738: 8733: 8729: 8708: 8705: 8702: 8699: 8694: 8690: 8686: 8683: 8680: 8677: 8674: 8669: 8665: 8661: 8658: 8655: 8652: 8649: 8644: 8640: 8615: 8604:Big O notation 8591: 8574: 8573: 8571: 8568: 8492: 8489: 8488: 8487: 8481: 8473: 8470: 8469: 8468: 8446: 8436: 8426: 8399: 8384:.NET Framework 8377: 8354:binarySearch() 8344: 8337:SearchFloat64s 8318: 8308: 8289:assumeSorted() 8270: 8244: 8218: 8215: 8201: 8179: 8153: 8149: 8146: 8143: 8137: 8134: 8113: 8091: 8070: 8050: 8030: 8027: 8024: 8002: 7998: 7995: 7992: 7967:overflow error 7942: 7936: 7933: 7872:Aegean Islands 7856: 200 BCE 7848: 7845: 7832: 7827: 7822: 7819: 7795: 7792: 7787: 7783: 7779: 7776: 7773: 7770: 7765: 7761: 7757: 7733: 7713: 7710: 7705: 7701: 7697: 7694: 7691: 7688: 7685: 7682: 7679: 7676: 7673: 7668: 7665: 7635: 7632: 7627: 7623: 7598: 7595: 7592: 7589: 7586: 7581: 7577: 7573: 7561: 7558: 7537: 7513: 7510: 7507: 7504: 7501: 7498: 7493: 7489: 7485: 7482: 7479: 7476: 7473: 7470: 7467: 7464: 7461: 7458: 7453: 7449: 7445: 7442: 7439: 7436: 7433: 7430: 7427: 7404: 7401: 7398: 7395: 7391: 7386: 7380: 7377: 7374: 7371: 7366: 7363: 7360: 7357: 7352: 7348: 7341: 7338: 7335: 7332: 7329: 7308: 7305: 7292: 7289: 7286: 7283: 7280: 7277: 7264: 7261: 7233: 7230: 7227: 7224: 7221: 7218: 7215: 7212: 7196:{\textstyle k} 7192: 7172: 7169: 7166: 7163: 7160: 7157: 7154: 7127:Main article: 7124: 7121: 7104: 7101: 7098: 7095: 7092: 7089: 7086: 7083: 7063: 7043: 7023: 7018: 7014: 7010: 7005: 7001: 6997: 6993: 6989: 6984: 6980: 6976: 6973: 6970: 6950: 6930: 6927: 6924: 6915:is the array, 6904: 6868:Main article: 6865: 6862: 6853:{\textstyle x} 6849: 6829: 6826: 6823: 6818: 6814: 6810: 6790: 6787: 6784: 6781: 6778: 6773: 6769: 6765: 6737:Main article: 6734: 6731: 6693: 6663:Main article: 6660: 6657: 6655: 6652: 6630: 6627: 6610: 6607: 6604: 6601: 6585:{\textstyle k} 6581: 6542: 6539: 6536: 6533: 6514:set membership 6509: 6506: 6480: 6477: 6453:{\textstyle n} 6449: 6409: 6406: 6392: 6389: 6386: 6383: 6380: 6377: 6374: 6346: 6343: 6329: 6326: 6323: 6320: 6317: 6314: 6303:set membership 6289: 6286: 6283: 6280: 6268: 6265: 6257:linear probing 6243:separate from 6226:floating-point 6216: 6213: 6204:{\textstyle n} 6200: 6180: 6177: 6174: 6171: 6168: 6165: 6162: 6157: 6153: 6149: 6136: 6133: 6121: 6118: 6115: 6112: 6109: 6105: 6099: 6096: 6093: 6090: 6087: 6084: 6081: 6076: 6072: 6068: 6064: 6060: 6057: 6054: 6051: 6048: 6045: 6042: 6039: 6034: 6030: 6026: 6023: 6017: 6014: 6011: 6008: 6005: 5998: 5995: 5992: 5989: 5986: 5983: 5980: 5975: 5971: 5967: 5963: 5959: 5956: 5953: 5950: 5947: 5944: 5941: 5938: 5935: 5930: 5926: 5922: 5919: 5916: 5913: 5910: 5907: 5904: 5898: 5895: 5892: 5889: 5885: 5882: 5859: 5856: 5853: 5849: 5846: 5825: 5822: 5819: 5816: 5792: 5789: 5786: 5783: 5780: 5777: 5774: 5769: 5765: 5761: 5757: 5753: 5750: 5747: 5744: 5741: 5738: 5735: 5732: 5729: 5724: 5720: 5716: 5713: 5710: 5707: 5704: 5701: 5698: 5695: 5692: 5689: 5686: 5682: 5678: 5675: 5670: 5667: 5663: 5659: 5656: 5653: 5650: 5647: 5644: 5639: 5635: 5630: 5625: 5621: 5617: 5613: 5610: 5607: 5604: 5601: 5598: 5593: 5589: 5584: 5580: 5577: 5574: 5571: 5568: 5564: 5560: 5557: 5554: 5551: 5548: 5545: 5542: 5539: 5536: 5533: 5530: 5527: 5524: 5502: 5499: 5496: 5493: 5473: 5470: 5450: 5427: 5424: 5421: 5401: 5381: 5378: 5375: 5352: 5349: 5346: 5341: 5338: 5335: 5332: 5326: 5323: 5320: 5317: 5313: 5310: 5289: 5286: 5283: 5280: 5260: 5237:external nodes 5232: 5229: 5216: 5194: 5190: 5186: 5183: 5180: 5177: 5174: 5171: 5168: 5165: 5160: 5156: 5152: 5149: 5144: 5141: 5138: 5135: 5132: 5129: 5126: 5121: 5117: 5113: 5109: 5105: 5102: 5099: 5096: 5093: 5090: 5087: 5084: 5081: 5076: 5072: 5068: 5065: 5060: 5056: 5053: 5048: 5045: 5041: 5037: 5034: 5031: 5028: 5025: 5022: 5017: 5013: 5008: 5003: 4999: 4995: 4991: 4988: 4985: 4982: 4979: 4976: 4971: 4967: 4962: 4958: 4955: 4952: 4949: 4946: 4940: 4937: 4934: 4931: 4928: 4925: 4922: 4900: 4897: 4894: 4891: 4871: 4868: 4865: 4862: 4840: 4837: 4832: 4829: 4825: 4821: 4818: 4815: 4812: 4809: 4806: 4801: 4797: 4792: 4787: 4783: 4779: 4775: 4772: 4769: 4766: 4763: 4760: 4755: 4751: 4746: 4742: 4739: 4736: 4733: 4730: 4727: 4723: 4719: 4716: 4713: 4710: 4705: 4701: 4696: 4690: 4685: 4682: 4679: 4675: 4671: 4668: 4665: 4662: 4659: 4637: 4634: 4631: 4628: 4606: 4603: 4598: 4595: 4590: 4587: 4582: 4579: 4557: 4554: 4551: 4548: 4545: 4542: 4539: 4536: 4533: 4530: 4527: 4524: 4521: 4518: 4515: 4512: 4509: 4506: 4502: 4498: 4495: 4492: 4489: 4484: 4480: 4475: 4469: 4464: 4461: 4458: 4454: 4427: 4423: 4420: 4417: 4414: 4409: 4405: 4400: 4394: 4389: 4386: 4383: 4379: 4375: 4372: 4369: 4366: 4363: 4341: 4316: 4312: 4309: 4306: 4303: 4297: 4294: 4291: 4288: 4285: 4282: 4279: 4259: 4256: 4253: 4250: 4230: 4206: 4203: 4200: 4180: 4164: 4161: 4148: 4145: 4142: 4122: 4105: 4102: 4085: 4082: 4079: 4076: 4064: 4061: 4037: 4034: 4031: 4028: 4025: 4021: 4015: 4012: 4009: 4006: 4003: 4000: 3997: 3992: 3988: 3984: 3980: 3976: 3973: 3970: 3967: 3964: 3961: 3958: 3955: 3950: 3946: 3942: 3922: 3919: 3916: 3913: 3910: 3907: 3902: 3898: 3877: 3873: 3869: 3866: 3863: 3860: 3857: 3854: 3851: 3848: 3843: 3839: 3835: 3832: 3827: 3824: 3821: 3818: 3815: 3812: 3809: 3804: 3800: 3796: 3792: 3788: 3785: 3782: 3779: 3776: 3773: 3770: 3767: 3764: 3759: 3755: 3751: 3728: 3725: 3722: 3719: 3716: 3711: 3707: 3703: 3683: 3680: 3677: 3674: 3671: 3668: 3665: 3660: 3656: 3652: 3636:{\textstyle n} 3632: 3609: 3606: 3603: 3600: 3597: 3594: 3591: 3586: 3582: 3578: 3552: 3548: 3536:floor function 3523: 3520: 3517: 3497: 3494: 3491: 3488: 3485: 3482: 3479: 3474: 3470: 3466: 3430: 3410: 3407: 3404: 3401: 3398: 3395: 3392: 3389: 3386: 3383: 3380: 3377: 3374: 3371: 3368: 3348: 3345: 3344: 3343: 3339: 3336: 3324: 3321: 3318: 3297: 3281: 3269: 3266: 3263: 3243: 3232: 3191: 3175: 3172: 3150: 3129: 3108: 3105: 3102: 3081: 3060: 3038: 3035: 3032: 3028: 3007: 3004: 2999: 2996: 2993: 2989: 2968: 2965: 2962: 2951: 2950: 2938: 2935: 2932: 2921: 2920: 2919: 2907: 2904: 2901: 2880: 2859: 2856: 2851: 2847: 2835: 2823: 2803: 2783: 2780: 2775: 2771: 2759: 2745: 2741: 2738: 2735: 2710: 2706: 2703: 2700: 2673: 2650: 2647: 2644: 2633: 2621: 2601: 2581: 2561: 2545: 2542: 2520: 2500: 2480: 2456: 2436: 2416: 2394: 2390: 2369: 2366: 2361: 2357: 2336: 2333: 2330: 2319: 2318: 2306: 2295: 2294: 2293: 2281: 2260: 2239: 2236: 2231: 2227: 2215: 2203: 2200: 2197: 2177: 2157: 2154: 2149: 2145: 2133: 2119: 2115: 2112: 2109: 2084: 2080: 2077: 2074: 2047: 2024: 2021: 2018: 2007: 1995: 1975: 1955: 1935: 1919: 1916: 1902: 1899: 1896: 1893: 1890: 1887: 1884: 1881: 1878: 1875: 1872: 1869: 1866: 1863: 1860: 1857: 1854: 1834: 1814: 1811: 1808: 1805: 1802: 1799: 1796: 1793: 1790: 1787: 1784: 1781: 1778: 1775: 1772: 1769: 1766: 1754: 1751: 1706: 1698: 1697: 1685: 1665: 1662: 1657: 1653: 1632: 1629: 1626: 1615: 1614: 1613: 1601: 1581: 1561: 1558: 1553: 1549: 1537: 1525: 1522: 1519: 1499: 1479: 1476: 1471: 1467: 1455: 1441: 1437: 1434: 1431: 1406: 1402: 1399: 1396: 1369: 1346: 1343: 1340: 1329: 1317: 1314: 1311: 1291: 1271: 1251: 1221: 1218: 1215: 1195: 1175: 1163: 1160: 1145: 1141: 1138: 1135: 1108:: 1072: 1056:floor function 1035: 1015: 1004: 1003: 991: 971: 968: 963: 959: 947: 935: 932: 929: 909: 889: 886: 881: 877: 865: 853: 850: 847: 827: 807: 804: 799: 795: 783: 769: 765: 762: 759: 734: 730: 727: 724: 697: 686: 674: 671: 668: 657: 645: 642: 639: 619: 599: 579: 555: 535: 511: 489: 486: 483: 479: 475: 472: 469: 464: 460: 456: 451: 447: 443: 438: 434: 411: 408: 405: 401: 397: 394: 391: 386: 382: 378: 373: 369: 365: 360: 356: 332: 312: 300: 297: 291: 288: 240: 220: 217: 214: 211: 208: 205: 153: 152: 149: 145: 144: 136: 127: 126: 114: 105: 104: 96: 87: 86: 74: 65: 64: 59: 58:Data structure 55: 54: 49: 45: 44: 41: 15: 9: 6: 4: 3: 2: 12140: 12129: 12126: 12124: 12121: 12119: 12116: 12114: 12111: 12109: 12106: 12104: 12101: 12100: 12098: 12083: 12080: 12078: 12075: 12074: 12071: 12065: 12062: 12060: 12057: 12055: 12052: 12050: 12047: 12045: 12042: 12040: 12037: 12035: 12032: 12030: 12027: 12025: 12022: 12020: 12017: 12015: 12014:Hash function 12012: 12010: 12007: 12005: 12002: 12000: 11997: 11995: 11992: 11990: 11987: 11985: 11982: 11980: 11977: 11975: 11972: 11970: 11969:Binary search 11967: 11965: 11962: 11961: 11959: 11955: 11949: 11946: 11944: 11941: 11939: 11936: 11934: 11931: 11929: 11926: 11924: 11921: 11919: 11916: 11914: 11911: 11909: 11906: 11904: 11901: 11899: 11896: 11894: 11891: 11889: 11886: 11884: 11881: 11880: 11878: 11874: 11870: 11866: 11859: 11854: 11852: 11847: 11845: 11840: 11839: 11836: 11830: 11826: 11823: 11820: 11818: 11815: 11814: 11803: 11797: 11793: 11789: 11785: 11780: 11772: 11764: 11758: 11754: 11753: 11748: 11744: 11740: 11734: 11730: 11726: 11722: 11717: 11713: 11707: 11703: 11699: 11695: 11694:Knuth, Donald 11691: 11687: 11681: 11677: 11673: 11669: 11668:Knuth, Donald 11665: 11661: 11655: 11651: 11647: 11643: 11642:Knuth, Donald 11639: 11635: 11629: 11625: 11620: 11616: 11610: 11606: 11602: 11598: 11594: 11590: 11584: 11580: 11576: 11571: 11567: 11561: 11557: 11556: 11551: 11547: 11543: 11539: 11535: 11531: 11525: 11521: 11517: 11512: 11508: 11502: 11498: 11494: 11489: 11485: 11479: 11475: 11471: 11467: 11463: 11462: 11440: 11436: 11432: 11422: 11415: 11410: 11394: 11390: 11386: 11380: 11364: 11361: 11357: 11353: 11347: 11331: 11328: 11324: 11320: 11314: 11298: 11294: 11290: 11284: 11268: 11264: 11260: 11256: 11250: 11234: 11230: 11226: 11222: 11216: 11200: 11196: 11192: 11186: 11178: 11174: 11168: 11153: 11149: 11143: 11136: 11131: 11115: 11111: 11107: 11103: 11097: 11090: 11085: 11066: 11062: 11058: 11053: 11048: 11044: 11040: 11039: 11031: 11024: 11008: 11004: 11000: 10996: 10995:Bloch, Joshua 10990: 10982: 10978: 10974: 10970: 10966: 10960: 10953: 10948: 10941: 10937: 10933: 10929: 10925: 10921: 10920: 10912: 10908: 10904: 10898: 10890: 10886: 10882: 10878: 10873: 10868: 10864: 10860: 10859: 10851: 10847: 10843: 10837: 10829: 10827:9780821813102 10823: 10818: 10813: 10809: 10805: 10801: 10794: 10787: 10783: 10780: 10777: 10774:"2−1". 10771: 10763: 10759: 10755: 10751: 10747: 10741: 10733: 10729: 10724: 10719: 10715: 10711: 10707: 10701: 10693: 10689: 10685: 10681: 10677: 10673: 10668: 10663: 10660:(3). 032335. 10659: 10655: 10648: 10640: 10636: 10632: 10628: 10623: 10618: 10614: 10610: 10609: 10601: 10593: 10589: 10585: 10581: 10574: 10565: 10560: 10556: 10552: 10548: 10541: 10532: 10527: 10523: 10519: 10515: 10511: 10507: 10501: 10492: 10487: 10483: 10479: 10475: 10468: 10457: 10453: 10447: 10443: 10439: 10435: 10434: 10425: 10418: 10410: 10406: 10401: 10396: 10392: 10388: 10381: 10362: 10358: 10354: 10350: 10346: 10341: 10336: 10332: 10328: 10321: 10317: 10311: 10296: 10290: 10286: 10282: 10278: 10274: 10273: 10268: 10262: 10260: 10258: 10249: 10245: 10240: 10235: 10231: 10227: 10226: 10221: 10219: 10210: 10203: 10198: 10191: 10186: 10184: 10182: 10175:, p. 33. 10174: 10169: 10162: 10157: 10150: 10145: 10137: 10133: 10129: 10125: 10120: 10115: 10111: 10107: 10106: 10098: 10089: 10084: 10080: 10073: 10071: 10059: 10055: 10048: 10047: 10039: 10037: 10029: 10024: 10005: 10002:. p. 1. 9998: 9997:"Hash tables" 9991: 9983: 9979: 9975: 9971: 9970: 9965: 9961: 9957: 9950: 9943: 9938: 9931: 9926: 9919: 9914: 9907: 9902: 9895: 9890: 9883: 9878: 9871: 9866: 9859: 9854: 9847: 9842: 9835: 9830: 9823: 9818: 9809: 9804: 9800: 9796: 9795: 9790: 9786: 9783:Beame, Paul; 9779: 9777: 9775: 9773: 9765: 9760: 9752: 9748: 9744: 9740: 9735: 9730: 9726: 9722: 9718: 9711: 9703: 9699: 9694: 9689: 9685: 9681: 9677: 9670: 9663: 9658: 9656: 9648: 9643: 9641: 9639: 9631: 9626: 9619: 9614: 9607: 9602: 9600: 9598: 9596: 9594: 9592: 9590: 9588: 9586: 9584: 9582: 9580: 9572: 9567: 9560: 9555: 9553: 9551: 9543: 9538: 9536: 9534: 9526: 9521: 9519: 9511: 9506: 9504: 9502: 9500: 9498: 9496: 9486: 9482: 9478: 9474: 9469: 9464: 9460: 9456: 9455: 9450: 9443: 9441: 9439: 9437: 9429: 9424: 9422: 9420: 9411: 9407: 9403: 9399: 9394: 9389: 9385: 9381: 9380: 9375: 9368: 9366: 9356: 9355: 9350: 9347: 9340: 9334:, p. 39. 9333: 9328: 9322:, p. 46. 9321: 9316: 9309: 9304: 9302: 9285: 9280: 9275: 9271: 9270: 9262: 9258: 9242: 9235: 9229: 9220: 9211: 9202: 9183: 9180: 9177: 9153: 9150: 9145: 9137: 9131: 9128: 9125: 9122: 9119: 9111: 9110:sentinel node 9095: 9092: 9089: 9086: 9083: 9080: 9072: 9068: 9063: 9044: 9041: 9038: 9035: 9030: 9026: 9022: 9002: 8999: 8996: 8993: 8988: 8984: 8980: 8972: 8968: 8963: 8944: 8941: 8938: 8935: 8932: 8929: 8909: 8889: 8869: 8860: 8859:external path 8856: 8840: 8832: 8813: 8810: 8805: 8802: 8794: 8778: 8770: 8769:internal path 8764: 8742: 8736: 8731: 8727: 8703: 8697: 8692: 8688: 8684: 8678: 8672: 8667: 8663: 8659: 8653: 8647: 8642: 8638: 8629: 8613: 8605: 8589: 8579: 8575: 8567: 8564: 8560: 8556: 8552: 8547: 8542: 8538: 8534: 8527: 8520: 8515: 8511: 8507: 8504:for external 8503: 8498: 8485: 8482: 8479: 8476: 8475: 8450: 8447: 8440: 8437: 8431:provides the 8430: 8427: 8423: 8418: 8413: 8408: 8404: 8400: 8389: 8385: 8381: 8378: 8366: 8360: 8352: 8348: 8345: 8341:SearchStrings 8322: 8319: 8313:provides the 8312: 8309: 8297:equaleRange() 8283:(returned by 8274: 8271: 8267:equal_range() 8263:upper_bound() 8259:lower_bound() 8252: 8248: 8245: 8242: 8235: 8232:provides the 8231: 8228: 8227: 8226: 8224: 8214: 8212: 8199: 8190: 8177: 8167: 8151: 8147: 8144: 8141: 8135: 8132: 8124: 8111: 8102: 8089: 8068: 8048: 8028: 8025: 8022: 8000: 7996: 7993: 7990: 7979: 7974: 7972: 7968: 7964: 7960: 7955: 7947: 7941: 7932: 7930: 7926: 7922: 7918: 7914: 7910: 7906: 7902: 7898: 7894: 7890: 7886: 7881: 7879: 7878: 7873: 7869: 7865: 7861: 7844: 7825: 7817: 7809: 7793: 7790: 7785: 7781: 7777: 7774: 7771: 7768: 7763: 7759: 7755: 7747: 7731: 7711: 7708: 7703: 7699: 7695: 7692: 7686: 7683: 7680: 7677: 7674: 7666: 7663: 7653: 7649: 7633: 7630: 7625: 7621: 7612: 7593: 7590: 7587: 7584: 7579: 7575: 7557: 7555: 7551: 7535: 7527: 7508: 7505: 7502: 7496: 7491: 7487: 7480: 7477: 7474: 7468: 7462: 7456: 7451: 7447: 7443: 7440: 7437: 7431: 7425: 7399: 7393: 7389: 7384: 7375: 7369: 7361: 7355: 7350: 7346: 7336: 7333: 7330: 7313: 7304: 7287: 7284: 7281: 7275: 7260: 7258: 7254: 7250: 7245: 7228: 7225: 7222: 7219: 7216: 7210: 7190: 7167: 7164: 7161: 7158: 7152: 7140: 7135: 7130: 7120: 7116: 7115:comparisons. 7099: 7096: 7093: 7090: 7087: 7081: 7061: 7041: 7016: 7012: 7008: 7003: 6999: 6991: 6982: 6978: 6974: 6971: 6948: 6928: 6925: 6922: 6902: 6894: 6889: 6881: 6876: 6871: 6861: 6847: 6824: 6821: 6816: 6812: 6785: 6782: 6779: 6776: 6771: 6767: 6750: 6745: 6740: 6730: 6728: 6691: 6683: 6675: 6671: 6666: 6651: 6649: 6645: 6641: 6637: 6626: 6624: 6605: 6599: 6579: 6571: 6567: 6563: 6562:Bloom filters 6558: 6556: 6537: 6531: 6523: 6519: 6515: 6505: 6502: 6498: 6497:hash function 6494: 6490: 6486: 6476: 6474: 6470: 6466: 6461: 6447: 6439: 6433: 6430: 6426: 6418: 6414: 6405: 6387: 6384: 6381: 6378: 6372: 6364: 6360: 6356: 6351: 6350:Linear search 6345:Linear search 6342: 6324: 6321: 6318: 6312: 6304: 6284: 6278: 6264: 6262: 6258: 6254: 6253:linear search 6250: 6246: 6242: 6238: 6233: 6231: 6227: 6223: 6212: 6198: 6175: 6172: 6166: 6160: 6155: 6151: 6132: 6116: 6113: 6110: 6103: 6097: 6094: 6085: 6079: 6074: 6070: 6062: 6058: 6055: 6052: 6043: 6037: 6032: 6028: 6021: 6012: 6009: 6006: 5996: 5993: 5984: 5978: 5973: 5969: 5961: 5957: 5951: 5948: 5939: 5933: 5928: 5924: 5911: 5908: 5905: 5896: 5890: 5883: 5880: 5871: 5854: 5847: 5844: 5820: 5814: 5805: 5790: 5787: 5778: 5772: 5767: 5763: 5755: 5751: 5745: 5742: 5733: 5727: 5722: 5718: 5705: 5702: 5699: 5693: 5690: 5687: 5684: 5680: 5676: 5673: 5668: 5665: 5661: 5654: 5651: 5648: 5642: 5637: 5633: 5628: 5623: 5619: 5615: 5608: 5605: 5602: 5596: 5591: 5587: 5582: 5575: 5572: 5569: 5562: 5558: 5555: 5552: 5549: 5543: 5537: 5534: 5528: 5522: 5514: 5497: 5491: 5471: 5468: 5448: 5439: 5425: 5422: 5419: 5399: 5379: 5376: 5373: 5350: 5347: 5344: 5336: 5330: 5324: 5318: 5311: 5308: 5284: 5278: 5258: 5250: 5246: 5245:external path 5242: 5238: 5228: 5214: 5205: 5192: 5188: 5181: 5178: 5169: 5163: 5158: 5154: 5147: 5142: 5139: 5130: 5124: 5119: 5115: 5107: 5100: 5097: 5094: 5085: 5079: 5074: 5070: 5063: 5058: 5054: 5051: 5046: 5043: 5039: 5032: 5029: 5026: 5020: 5015: 5011: 5006: 5001: 4997: 4993: 4986: 4983: 4980: 4974: 4969: 4965: 4960: 4953: 4950: 4947: 4938: 4935: 4932: 4926: 4920: 4912: 4895: 4889: 4866: 4860: 4851: 4838: 4835: 4830: 4827: 4823: 4816: 4813: 4810: 4804: 4799: 4795: 4790: 4785: 4781: 4777: 4770: 4767: 4764: 4758: 4753: 4749: 4744: 4737: 4734: 4731: 4725: 4721: 4714: 4708: 4703: 4699: 4694: 4688: 4683: 4680: 4677: 4673: 4669: 4663: 4657: 4649: 4632: 4626: 4604: 4601: 4596: 4593: 4588: 4585: 4580: 4577: 4568: 4555: 4552: 4549: 4546: 4543: 4540: 4534: 4528: 4525: 4519: 4513: 4510: 4507: 4504: 4500: 4493: 4487: 4482: 4478: 4473: 4467: 4462: 4459: 4456: 4452: 4443: 4439: 4425: 4418: 4412: 4407: 4403: 4398: 4392: 4387: 4384: 4381: 4377: 4373: 4367: 4361: 4353: 4339: 4330: 4314: 4307: 4301: 4295: 4292: 4289: 4283: 4277: 4254: 4248: 4228: 4220: 4204: 4201: 4198: 4178: 4170: 4169:internal path 4160: 4146: 4143: 4140: 4120: 4112: 4101: 4099: 4080: 4074: 4060: 4058: 4052: 4049: 4032: 4029: 4026: 4019: 4013: 4010: 4001: 3995: 3990: 3986: 3978: 3974: 3971: 3968: 3959: 3953: 3948: 3944: 3920: 3917: 3911: 3905: 3900: 3896: 3875: 3871: 3864: 3861: 3852: 3846: 3841: 3837: 3830: 3825: 3822: 3813: 3807: 3802: 3798: 3790: 3783: 3780: 3777: 3768: 3762: 3757: 3753: 3740: 3720: 3714: 3709: 3705: 3678: 3675: 3669: 3663: 3658: 3654: 3630: 3621: 3604: 3601: 3595: 3589: 3584: 3580: 3568: 3550: 3546: 3537: 3518: 3492: 3489: 3483: 3477: 3472: 3468: 3455: 3447: 3428: 3405: 3402: 3399: 3396: 3393: 3390: 3387: 3384: 3381: 3378: 3375: 3372: 3369: 3358: 3353: 3340: 3337: 3322: 3319: 3316: 3308: 3295: 3286: 3282: 3267: 3264: 3261: 3241: 3233: 3230: 3226: 3222: 3221: 3220: 3218: 3217:Range queries 3214: 3209: 3189: 3180: 3169: 3165: 3161: 3157: 3153: 3149: 3142: 3140: 3127: 3106: 3103: 3100: 3092: 3079: 3058: 3036: 3033: 3030: 3026: 3005: 3002: 2997: 2994: 2991: 2987: 2966: 2963: 2960: 2936: 2933: 2930: 2922: 2905: 2902: 2899: 2891: 2878: 2857: 2854: 2849: 2845: 2836: 2821: 2801: 2781: 2778: 2773: 2769: 2760: 2743: 2739: 2736: 2733: 2708: 2704: 2701: 2698: 2687: 2671: 2663: 2662: 2648: 2645: 2642: 2634: 2619: 2599: 2579: 2559: 2551: 2550: 2549: 2539: 2535: 2531: 2527: 2523: 2519: 2512: 2498: 2478: 2470: 2454: 2434: 2414: 2392: 2388: 2367: 2364: 2359: 2355: 2334: 2331: 2328: 2304: 2296: 2279: 2271: 2258: 2237: 2234: 2229: 2225: 2216: 2201: 2198: 2195: 2175: 2155: 2152: 2147: 2143: 2134: 2117: 2113: 2110: 2107: 2082: 2078: 2075: 2072: 2061: 2045: 2037: 2036: 2022: 2019: 2016: 2008: 1993: 1973: 1953: 1933: 1925: 1924: 1923: 1915: 1897: 1894: 1891: 1888: 1885: 1882: 1879: 1876: 1873: 1870: 1867: 1864: 1861: 1858: 1855: 1832: 1809: 1806: 1803: 1800: 1797: 1794: 1791: 1788: 1785: 1782: 1779: 1776: 1773: 1770: 1767: 1749:unsuccessful 1748: 1744: 1741: 1737: 1733: 1729: 1725: 1721: 1717: 1713: 1709: 1705: 1683: 1663: 1660: 1655: 1651: 1630: 1627: 1624: 1616: 1599: 1579: 1559: 1556: 1551: 1547: 1538: 1523: 1520: 1517: 1497: 1477: 1474: 1469: 1465: 1456: 1439: 1435: 1432: 1429: 1404: 1400: 1397: 1394: 1383: 1367: 1359: 1358: 1344: 1341: 1338: 1330: 1315: 1312: 1309: 1289: 1269: 1249: 1241: 1240: 1239: 1237: 1233: 1219: 1216: 1213: 1193: 1173: 1159: 1143: 1139: 1136: 1133: 1122: 1116:unsuccessful 1115: 1111: 1107: 1103: 1099: 1095: 1091: 1087: 1083: 1079: 1075: 1069:binary-search 1067: 1063: 1057: 1049: 1033: 1013: 989: 969: 966: 961: 957: 948: 933: 930: 927: 907: 887: 884: 879: 875: 866: 851: 848: 845: 825: 805: 802: 797: 793: 784: 767: 763: 760: 757: 732: 728: 725: 722: 711: 695: 687: 672: 669: 666: 658: 643: 640: 637: 617: 597: 577: 569: 568: 567: 553: 533: 525: 509: 487: 484: 481: 477: 473: 470: 467: 462: 458: 454: 449: 445: 441: 436: 432: 409: 406: 403: 399: 395: 392: 389: 384: 380: 376: 371: 367: 363: 358: 354: 346: 330: 310: 296: 287: 285: 281: 277: 273: 269: 264: 262: 258: 254: 253:linear search 238: 215: 212: 209: 203: 195: 191: 186: 184: 180: 176: 172: 168: 164: 163:binary search 160: 150: 146: 143: 141: 137: 135: 132: 128: 125: 123: 119: 115: 113: 110: 106: 103: 101: 97: 95: 92: 88: 85: 83: 79: 75: 73: 70: 66: 63: 60: 56: 53: 50: 46: 39: 34: 31:Binary search 28: 26: 22: 12039:Root-finding 11968: 11964:Backtracking 11928:Segment tree 11898:Fenwick tree 11791: 11751: 11720: 11697: 11671: 11645: 11623: 11600: 11574: 11554: 11515: 11492: 11469: 11466:Bentley, Jon 11443:. Retrieved 11434: 11421: 11409: 11397:. Retrieved 11388: 11379: 11367:. Retrieved 11355: 11346: 11334:. Retrieved 11322: 11313: 11301:. Retrieved 11292: 11283: 11271:. Retrieved 11258: 11249: 11237:. Retrieved 11224: 11215: 11203:. Retrieved 11194: 11185: 11176: 11167: 11155:. Retrieved 11151: 11142: 11130: 11118:. Retrieved 11105: 11096: 11089:Bentley 2000 11084: 11072:. Retrieved 11045:(2): 67–71. 11042: 11036: 11023: 11011:. Retrieved 11002: 10989: 10972: 10968: 10959: 10952:Bentley 2000 10947: 10923: 10919:Algorithmica 10917: 10897: 10862: 10858:Algorithmica 10856: 10836: 10807: 10803: 10793: 10770: 10753: 10749: 10740: 10709: 10700: 10657: 10653: 10647: 10612: 10608:Algorithmica 10606: 10600: 10583: 10579: 10573: 10554: 10550: 10540: 10517: 10500: 10481: 10477: 10467: 10430: 10417: 10386: 10380: 10368:. Retrieved 10330: 10326: 10310: 10298:. Retrieved 10271: 10229: 10223: 10217: 10209: 10197: 10168: 10156: 10144: 10109: 10103: 10097: 10078: 10045: 10023: 10011:. Retrieved 9995:Morin, Pat. 9990: 9973: 9967: 9956:Karlin, Anna 9949: 9937: 9925: 9913: 9901: 9889: 9877: 9865: 9853: 9841: 9829: 9817: 9801:(1): 38–72. 9798: 9792: 9759: 9724: 9720: 9710: 9686:(4): 15–19. 9683: 9679: 9669: 9625: 9613: 9566: 9458: 9452: 9383: 9377: 9352: 9339: 9327: 9315: 9288:. Retrieved 9268: 9261: 9241: 9228: 9219: 9210: 9201: 9062: 8962: 8858: 8830: 8792: 8768: 8763: 8578: 8536: 8532: 8514:CC-BY-SA-3.0 8501: 8494: 8392:System.Array 8301:lowerBound() 8220: 8192: 8170: 8168: 8104: 8082: 7975: 7962: 7951: 7946:Donald Knuth 7939: 7885:John Mauchly 7882: 7875: 7850: 7651: 7563: 7318: 7266: 7246: 7183:time, where 7144: 7117: 6890: 6886: 6754: 6682:lookup table 6679: 6640:fusion trees 6632: 6559: 6511: 6482: 6462: 6434: 6422: 6348: 6270: 6234: 6230:real numbers 6218: 6138: 5872: 5806: 5515: 5440: 5248: 5244: 5240: 5236: 5234: 5207:For integer 5206: 4913: 4852: 4650: 4569: 4444: 4440: 4354: 4331: 4218: 4168: 4166: 4107: 4066: 4056: 4053: 4050: 3741: 3622: 3456: 3452: 3288: 3228: 3207: 3205: 3167: 3163: 3159: 3155: 3151: 3143: 3120: 3072: 2952: 2871: 2547: 2537: 2533: 2529: 2525: 2521: 2513: 2320: 2251: 1921: 1756: 1746: 1742: 1739: 1735: 1731: 1727: 1723: 1719: 1718:L != R 1715: 1711: 1707: 1699: 1234: 1165: 1118: 1113: 1109: 1105: 1101: 1097: 1093: 1089: 1085: 1081: 1077: 1073: 1060:unsuccessful 1005: 302: 293: 265: 187: 183:sorted array 174: 170: 166: 162: 156: 139: 121: 117: 99: 81: 77: 27: 25: 11918:Linked list 10975:: 190–194. 10810:: 180–181. 10586:: 505–516. 8403:Objective-C 8365:Collections 8281:SortedRange 7954:Jon Bentley 7923:introduced 7864:reciprocals 7860:sexagesimal 7253:data mining 6704:) would be 6489:hash tables 6473:filesystems 6429:binary tree 6261:hash tables 5392:instead of 4159:intervals. 3347:Performance 261:hash tables 175:binary chop 112:performance 94:performance 72:performance 12128:2 (number) 12097:Categories 12054:Sweep line 12029:Randomized 11957:Algorithms 11908:Hash table 11869:algorithms 11752:Algorithms 11360:Apple Inc. 11327:Apple Inc. 10400:1503.00805 10202:Knuth 1998 10190:Knuth 1998 10161:Knuth 1998 10149:Knuth 1998 10028:Knuth 2011 9942:Knuth 1998 9930:Knuth 1998 9918:Knuth 1998 9906:Knuth 1998 9882:Knuth 1998 9846:Knuth 1998 9834:Knuth 1998 9822:Knuth 1998 9764:Knuth 1997 9734:1509.05053 9717:Morin, Pat 9662:Knuth 1998 9647:Knuth 1997 9630:Chang 2003 9618:Knuth 1998 9606:Knuth 1998 9510:Knuth 1998 9428:Knuth 1998 9308:Knuth 1998 9067:Knuth 1998 8967:Knuth 1998 8855:Knuth 1998 8394:'s method 8351:overloaded 8333:SearchInts 8315:SEARCH ALL 8293:contains() 7959:edge cases 7877:Catholicon 7866:sorted in 6654:Variations 6648:bit arrays 6555:Judy array 6363:merge sort 3071:. Even if 2427:. Even if 1048:pseudocode 524:subroutine 194:worst case 131:Worst-case 69:Worst-case 12049:Streaming 12034:Recursion 11605:CRC Press 11352:"CFArray" 11319:"NSArray" 11152:dlang.org 11047:CiteSeerX 10867:CiteSeerX 10357:0022-0000 10335:CiteSeerX 10114:CiteSeerX 9477:0004-5411 9402:0001-0782 9354:MathWorld 9253:Citations 9132:− 9093:− 9087:⁡ 9042:− 9036:⁡ 8994:⁡ 8939:− 8737:⁡ 8698:⁡ 8685:÷ 8673:⁡ 8648:⁡ 8628:logarithm 8563:Q81434400 8555:2470-6345 8516:license ( 8508:in 2018 ( 8425:function. 8380:Microsoft 8370:java.util 8305:trisect() 8277:std.range 8237:bsearch() 8145:− 7883:In 1946, 7843:queries. 7791:⁡ 7775:≈ 7769:⁡ 7709:⁡ 7693:≈ 7684:− 7678:⁡ 7667:π 7631:⁡ 7597:⌋ 7585:⁡ 7572:⌊ 7536:τ 7506:− 7497:⁡ 7478:− 7469:− 7457:⁡ 7441:− 7385:− 7356:⁡ 7337:τ 7334:− 7285:⁡ 7259:routing. 7226:⁡ 7165:⁡ 7097:⁡ 7091:⁡ 7009:− 6975:− 6883:location. 6828:⌋ 6822:⁡ 6809:⌊ 6789:⌋ 6777:⁡ 6764:⌊ 6570:bit array 6518:bit array 6501:amortized 6469:databases 6385:⁡ 6359:quicksort 6322:⁡ 6237:processor 6179:⌋ 6161:⁡ 6148:⌊ 6092:⌋ 6080:⁡ 6067:⌊ 6059:− 6050:⌋ 6038:⁡ 6025:⌊ 5991:⌋ 5979:⁡ 5966:⌊ 5958:− 5946:⌋ 5934:⁡ 5921:⌊ 5785:⌋ 5773:⁡ 5760:⌊ 5752:− 5740:⌋ 5728:⁡ 5715:⌊ 5643:⁡ 5620:− 5597:⁡ 5179:− 5176:⌋ 5164:⁡ 5151:⌊ 5148:− 5137:⌋ 5125:⁡ 5112:⌊ 5101:− 5092:⌋ 5080:⁡ 5067:⌊ 5021:⁡ 4998:− 4975:⁡ 4805:⁡ 4782:− 4759:⁡ 4709:⁡ 4674:∑ 4488:⁡ 4453:∑ 4413:⁡ 4378:∑ 4111:intervals 4008:⌋ 3996:⁡ 3983:⌊ 3975:− 3966:⌋ 3954:⁡ 3941:⌊ 3918:− 3906:⁡ 3862:− 3859:⌋ 3847:⁡ 3834:⌊ 3831:− 3820:⌋ 3808:⁡ 3795:⌊ 3784:− 3775:⌋ 3763:⁡ 3750:⌊ 3727:⌋ 3715:⁡ 3702:⌊ 3682:⌋ 3664:⁡ 3651:⌊ 3608:⌋ 3590:⁡ 3577:⌊ 3522:⌋ 3519:⋅ 3516:⌊ 3496:⌋ 3478:⁡ 3465:⌊ 3265:− 3229:less than 3104:− 3034:− 2995:− 2934:− 2855:≤ 2235:≥ 1726:A > T 1676:, return 1557:≤ 1521:− 1342:≠ 1313:− 1100:A > T 1092:A < T 931:− 641:− 485:− 474:≤ 471:⋯ 468:≤ 455:≤ 442:≤ 407:− 393:… 299:Procedure 290:Algorithm 213:⁡ 196:, making 91:Best-case 11825:Archived 11790:(2013). 11696:(2011). 11670:(1998). 11644:(1997). 11552:(2009). 11468:(2000). 11399:26 March 11393:Archived 11363:Archived 11330:Archived 11303:10 April 11297:Archived 11267:Archived 11233:Archived 11205:28 April 11199:Archived 11175:(2012), 11157:29 April 11120:28 March 11114:Archived 11112:. 2013. 11074:19 March 11065:Archived 11013:21 April 11007:Archived 10940:11232235 10909:(1986), 10889:12745042 10848:(1986). 10782:Archived 10708:(1996). 10692:41539957 10639:13717616 10456:Archived 10361:Archived 10248:11089655 10058:archived 10013:28 March 10004:Archived 9787:(2001). 9751:23752485 9702:23752485 9485:13406983 9410:43325465 9284:Archived 8719:, where 8559:Wikidata 8539:(1): 5. 8472:See also 8234:function 8191:exceeds 7943:— 7901:ALGOL 60 6495:using a 5884:′ 5848:′ 5662:⌋ 5629:⌊ 5616:⌋ 5583:⌊ 5312:′ 5040:⌋ 5007:⌊ 4994:⌋ 4961:⌊ 4824:⌋ 4791:⌊ 4778:⌋ 4745:⌊ 4722:⌋ 4695:⌊ 4501:⌋ 4474:⌊ 4426:⌋ 4399:⌊ 4098:word RAM 3152:function 2522:function 1708:function 1074:function 12044:Sorting 12019:Minimax 11458:Sources 10779:A000225 10712:. 28th 10672:Bibcode 10592:0143666 10520:. 10th 10389:. 48th 10370:30 June 10300:30 June 10275:. 33rd 10220:search" 10136:7931252 9290:29 June 8922:nodes, 8791:be the 8626:is the 8443:bsearch 8388:generic 8239:in its 7847:History 7744:is the 7524:is the 6493:records 6479:Hashing 4096:in the 3565:is the 3018:, then 2923:Return 2467:is the 2380:, then 2297:Return 1382:ceiling 1121:ceiling 1098:else if 1054:is the 345:records 192:in the 177:, is a 148:Optimal 109:Average 12024:Online 12009:Greedy 11938:String 11798: 11759: 11735: 11708: 11682: 11656: 11630: 11611: 11585: 11562: 11526: 11503: 11480: 11445:25 May 11441:. 2024 11173:Unisys 11049: 10938: 10887: 10869: 10824: 10690: 10637: 10590: 10448: 10355: 10337: 10291: 10246: 10134: 10116: 9749: 9700: 9483: 9475: 9408: 9400: 8606:, and 8561: 8553: 8463:, and 8433:bisect 8429:Python 8405:, the 8359:Arrays 8339:, and 8329:Search 8285:sort() 7650:. Any 6646:, and 6465:B-tree 3170:R - 1 3168:return 3144:Where 2870:; set 2837:Else, 2794:, set 2635:While 2538:return 2514:Where 2250:; set 2217:Else, 2168:, set 2009:While 1747:return 1745:L 1743:return 1738:A = T 1700:Where 1572:; set 1539:Else, 1490:, set 1331:While 1114:return 1112:m 1110:return 1084:L ≤ R 1058:, and 900:, set 818:, set 284:B-tree 11933:Stack 11923:Queue 11903:Graph 11883:Array 11429:slice 11369:1 May 11336:1 May 11273:1 May 11239:1 May 11068:(PDF) 11033:(PDF) 10936:S2CID 10914:(PDF) 10885:S2CID 10853:(PDF) 10718:arXiv 10688:S2CID 10662:arXiv 10635:S2CID 10617:arXiv 10459:(PDF) 10431:49th 10427:(PDF) 10395:arXiv 10364:(PDF) 10323:(PDF) 10244:S2CID 10132:S2CID 10061:(PDF) 10050:(PDF) 10007:(PDF) 10000:(PDF) 9747:S2CID 9729:arXiv 9698:S2CID 9481:S2CID 9406:S2CID 8831:after 8570:Notes 8529:(PDF) 8407:Cocoa 8311:COBOL 7952:When 7778:0.433 7652:exact 6895:. If 6644:tries 6427:is a 6408:Trees 6241:cache 4191:, is 3208:exact 3156:while 3146:floor 2686:floor 2526:while 2516:floor 2060:floor 1716:while 1082:while 1052:floor 710:floor 173:, or 120:(log 80:(log 62:Array 48:Class 12004:Fold 11948:Trie 11943:Tree 11913:Heap 11867:and 11796:ISBN 11757:ISBN 11733:ISBN 11706:ISBN 11680:ISBN 11654:ISBN 11628:ISBN 11609:ISBN 11583:ISBN 11560:ISBN 11524:ISBN 11501:ISBN 11478:ISBN 11447:2024 11401:2018 11371:2016 11338:2016 11305:2016 11275:2016 11241:2016 11207:2016 11159:2020 11122:2016 11076:2016 11015:2016 10822:ISBN 10776:OEIS 10446:ISBN 10372:2018 10353:ISSN 10302:2018 10289:ISBN 10015:2016 9473:ISSN 9398:ISSN 9292:2018 9181:> 9120:1.75 8981:17.5 8582:The 8551:ISSN 8519:2019 8449:Rust 8439:Ruby 8401:For 8374:List 8362:and 8347:Java 8325:sort 8303:and 8287:and 8265:and 8103:and 8061:and 7919:and 7696:0.22 7528:and 7255:and 7054:and 6522:bits 6471:and 6361:and 6255:and 6222:bits 3357:tree 3164:else 2979:and 2964:> 2779:> 2664:Set 2646:< 2592:and 2552:Set 2534:else 2469:rank 2347:and 2332:< 2153:< 2038:Set 2020:< 1966:and 1926:Set 1740:then 1732:else 1728:then 1702:ceil 1617:Now 1475:> 1360:Set 1282:and 1242:Set 1106:else 1102:then 1094:then 1026:and 949:Now 885:> 803:< 688:Set 670:> 610:and 570:Set 282:and 11725:doi 11057:doi 10977:doi 10928:doi 10877:doi 10812:doi 10758:doi 10728:doi 10680:doi 10627:doi 10559:doi 10555:270 10526:doi 10486:doi 10438:doi 10405:doi 10345:doi 10281:doi 10234:doi 10124:doi 10083:doi 9978:doi 9803:doi 9739:doi 9688:doi 9463:doi 9388:doi 9274:doi 9129:8.5 9084:log 9071:MIX 9027:log 8985:log 8971:MIX 8728:log 8689:log 8664:log 8639:log 8614:log 8602:is 8541:doi 8382:'s 8323:'s 8249:'s 8247:C++ 7782:log 7764:605 7760:log 7700:log 7622:log 7576:log 7488:log 7448:log 7347:log 7282:log 7223:log 7162:log 7137:In 7094:log 7088:log 6813:log 6768:log 6566:set 6382:log 6319:log 6259:in 6245:RAM 6152:log 6071:log 6029:log 5970:log 5925:log 5764:log 5719:log 5634:log 5588:log 5155:log 5116:log 5071:log 5012:log 4966:log 4796:log 4750:log 4700:log 4479:log 4404:log 4057:all 3987:log 3945:log 3897:log 3838:log 3799:log 3754:log 3706:log 3655:log 3581:log 3547:log 3469:log 3406:100 2953:If 2892:to 2814:to 2761:If 2688:of 2612:to 2572:to 2471:of 2321:If 2272:to 2188:to 2135:If 2062:of 1986:to 1946:to 1592:to 1510:to 1457:If 1384:of 1302:to 1262:to 1123:of 920:to 867:If 838:to 785:If 712:of 659:If 630:to 590:to 546:in 323:of 210:log 157:In 151:Yes 142:(1) 102:(1) 12099:: 11731:. 11700:. 11674:. 11648:. 11607:. 11581:. 11548:; 11544:; 11540:; 11522:. 11499:. 11476:. 11437:. 11433:. 11387:. 11358:. 11354:. 11325:. 11321:. 11295:. 11291:. 11265:. 11261:. 11257:. 11231:. 11227:. 11223:. 11197:. 11193:. 11150:. 11104:. 11063:. 11055:. 11043:87 11041:. 11035:. 11005:. 11001:. 10973:20 10971:. 10934:, 10922:, 10916:, 10905:; 10883:. 10875:. 10861:. 10855:. 10844:; 10820:. 10808:10 10806:. 10802:. 10752:. 10726:. 10686:. 10678:. 10670:. 10658:75 10656:. 10633:. 10625:. 10613:34 10611:. 10588:MR 10553:. 10549:. 10524:. 10512:; 10508:; 10482:63 10480:. 10476:. 10454:. 10444:. 10429:. 10403:. 10359:. 10351:. 10343:. 10331:68 10329:. 10325:. 10287:. 10256:^ 10242:. 10230:21 10228:. 10222:. 10180:^ 10130:. 10122:. 10110:13 10108:. 10069:^ 10052:, 10035:^ 9974:23 9972:. 9958:; 9799:65 9797:. 9791:. 9771:^ 9745:. 9737:. 9725:22 9723:. 9696:. 9684:32 9682:. 9678:. 9654:^ 9637:^ 9578:^ 9549:^ 9532:^ 9517:^ 9494:^ 9479:. 9471:. 9457:. 9451:. 9435:^ 9418:^ 9404:. 9396:. 9384:14 9382:. 9376:. 9364:^ 9351:. 9300:^ 9282:. 9184:44 9096:16 9081:18 9045:16 9023:18 9003:17 8557:. 8549:. 8535:. 8531:. 8467:. 8459:, 8455:, 8335:, 8331:, 8321:Go 8299:, 8295:, 8261:, 8257:, 8166:. 7931:. 7874:. 7853:c. 7732:ln 7675:ln 7390:10 6729:. 6642:, 6638:, 6625:. 6487:, 6475:. 6423:A 6211:. 5513:: 4911:: 4586:10 4556:10 3429:40 3400:90 3394:80 3388:50 3382:40 3376:30 3370:20 3355:A 3215:. 3160:if 3141:. 2661:, 2540:L 2530:if 2511:. 2035:, 1736:if 1724:if 1720:do 1712:is 1357:, 1090:if 1086:do 1078:is 566:. 169:, 161:, 11857:e 11850:t 11843:v 11804:. 11783:. 11765:. 11741:. 11727:: 11714:. 11688:. 11662:. 11636:. 11617:. 11591:. 11568:. 11532:. 11509:. 11486:. 11449:. 11431:" 11403:. 11373:. 11340:. 11307:. 11277:. 11243:. 11209:. 11161:. 11124:. 11078:. 11059:: 11017:. 10983:. 10979:: 10930:: 10924:1 10891:. 10879:: 10863:1 10830:. 10814:: 10764:. 10760:: 10754:1 10734:. 10730:: 10720:: 10694:. 10682:: 10674:: 10664:: 10641:. 10629:: 10619:: 10594:. 10584:6 10567:. 10561:: 10534:. 10528:: 10494:. 10488:: 10440:: 10411:. 10407:: 10397:: 10374:. 10347:: 10304:. 10283:: 10250:. 10236:: 10218:n 10138:. 10126:: 10091:. 10085:: 10017:. 9984:. 9980:: 9811:. 9805:: 9753:. 9741:: 9731:: 9704:. 9690:: 9487:. 9465:: 9459:9 9412:. 9390:: 9357:. 9294:. 9276:: 9196:. 9178:n 9154:n 9151:4 9146:2 9138:n 9126:+ 9123:n 9090:n 9039:n 9031:2 9000:+ 8997:n 8989:2 8945:n 8942:2 8936:E 8933:= 8930:I 8910:n 8890:E 8870:I 8841:I 8814:n 8811:I 8806:+ 8803:1 8779:I 8746:) 8743:b 8740:( 8732:k 8707:) 8704:b 8701:( 8693:k 8682:) 8679:n 8676:( 8668:k 8660:= 8657:) 8654:n 8651:( 8643:b 8590:O 8565:. 8543:: 8537:2 8398:. 8273:D 8269:. 8230:C 8200:R 8178:L 8152:2 8148:L 8142:R 8136:+ 8133:L 8112:R 8090:L 8069:R 8049:L 8029:R 8026:+ 8023:L 8001:2 7997:R 7994:+ 7991:L 7831:) 7826:n 7821:( 7818:O 7794:n 7786:2 7772:n 7756:4 7712:n 7704:2 7690:) 7687:1 7681:n 7672:( 7664:1 7634:n 7626:2 7594:1 7591:+ 7588:n 7580:2 7512:) 7509:p 7503:1 7500:( 7492:2 7484:) 7481:p 7475:1 7472:( 7466:) 7463:p 7460:( 7452:2 7444:p 7438:= 7435:) 7432:p 7429:( 7426:H 7403:) 7400:p 7397:( 7394:H 7379:) 7376:p 7373:( 7370:H 7365:) 7362:n 7359:( 7351:2 7340:) 7331:1 7328:( 7291:) 7288:n 7279:( 7276:O 7232:) 7229:n 7220:+ 7217:k 7214:( 7211:O 7191:k 7171:) 7168:n 7159:k 7156:( 7153:O 7103:) 7100:n 7085:( 7082:O 7062:R 7042:L 7022:) 7017:L 7013:A 7004:R 7000:A 6996:( 6992:/ 6988:) 6983:L 6979:A 6972:T 6969:( 6949:T 6929:R 6926:, 6923:L 6903:A 6848:x 6825:x 6817:2 6786:1 6783:+ 6780:x 6772:2 6722:6 6718:3 6714:9 6710:3 6706:6 6692:m 6609:) 6606:k 6603:( 6600:O 6580:k 6541:) 6538:1 6535:( 6532:O 6448:n 6391:) 6388:n 6379:n 6376:( 6373:O 6328:) 6325:n 6316:( 6313:O 6288:) 6285:n 6282:( 6279:O 6199:n 6176:1 6173:+ 6170:) 6167:n 6164:( 6156:2 6120:) 6117:1 6114:+ 6111:n 6108:( 6104:/ 6098:1 6095:+ 6089:) 6086:n 6083:( 6075:2 6063:2 6056:2 6053:+ 6047:) 6044:n 6041:( 6033:2 6022:= 6016:) 6013:1 6010:+ 6007:n 6004:( 5997:1 5994:+ 5988:) 5985:n 5982:( 5974:2 5962:2 5955:) 5952:2 5949:+ 5943:) 5940:n 5937:( 5929:2 5918:( 5915:) 5912:1 5909:+ 5906:n 5903:( 5897:= 5894:) 5891:n 5888:( 5881:T 5858:) 5855:n 5852:( 5845:T 5824:) 5821:n 5818:( 5815:E 5791:1 5788:+ 5782:) 5779:n 5776:( 5768:2 5756:2 5749:) 5746:2 5743:+ 5737:) 5734:n 5731:( 5723:2 5712:( 5709:) 5706:1 5703:+ 5700:n 5697:( 5694:= 5691:n 5688:2 5685:+ 5681:] 5677:2 5674:+ 5669:1 5666:+ 5658:) 5655:1 5652:+ 5649:n 5646:( 5638:2 5624:2 5612:) 5609:1 5606:+ 5603:n 5600:( 5592:2 5579:) 5576:1 5573:+ 5570:n 5567:( 5563:[ 5559:= 5556:n 5553:2 5550:+ 5547:) 5544:n 5541:( 5538:I 5535:= 5532:) 5529:n 5526:( 5523:E 5501:) 5498:n 5495:( 5492:I 5472:n 5469:2 5449:n 5426:1 5423:+ 5420:n 5400:n 5380:1 5377:+ 5374:n 5351:1 5348:+ 5345:n 5340:) 5337:n 5334:( 5331:E 5325:= 5322:) 5319:n 5316:( 5309:T 5288:) 5285:n 5282:( 5279:E 5259:n 5215:n 5193:n 5189:/ 5185:) 5182:2 5173:) 5170:n 5167:( 5159:2 5143:1 5140:+ 5134:) 5131:n 5128:( 5120:2 5108:2 5104:( 5098:1 5095:+ 5089:) 5086:n 5083:( 5075:2 5064:= 5059:n 5055:2 5052:+ 5047:1 5044:+ 5036:) 5033:1 5030:+ 5027:n 5024:( 5016:2 5002:2 4990:) 4987:1 4984:+ 4981:n 4978:( 4970:2 4957:) 4954:1 4951:+ 4948:n 4945:( 4939:+ 4936:1 4933:= 4930:) 4927:n 4924:( 4921:T 4899:) 4896:n 4893:( 4890:T 4870:) 4867:n 4864:( 4861:I 4839:2 4836:+ 4831:1 4828:+ 4820:) 4817:1 4814:+ 4811:n 4808:( 4800:2 4786:2 4774:) 4771:1 4768:+ 4765:n 4762:( 4754:2 4741:) 4738:1 4735:+ 4732:n 4729:( 4726:= 4718:) 4715:k 4712:( 4704:2 4689:n 4684:1 4681:= 4678:k 4670:= 4667:) 4664:n 4661:( 4658:I 4636:) 4633:n 4630:( 4627:I 4605:7 4602:3 4597:2 4594:= 4589:7 4581:+ 4578:1 4553:= 4550:8 4547:+ 4544:2 4541:= 4538:) 4535:2 4532:( 4529:4 4526:+ 4523:) 4520:1 4517:( 4514:2 4511:+ 4508:0 4505:= 4497:) 4494:k 4491:( 4483:2 4468:7 4463:1 4460:= 4457:k 4422:) 4419:k 4416:( 4408:2 4393:n 4388:1 4385:= 4382:k 4374:= 4371:) 4368:n 4365:( 4362:I 4340:n 4315:n 4311:) 4308:n 4305:( 4302:I 4296:+ 4293:1 4290:= 4287:) 4284:n 4281:( 4278:T 4258:) 4255:n 4252:( 4249:I 4229:n 4205:1 4202:+ 4199:l 4179:l 4147:1 4144:+ 4141:n 4121:n 4084:) 4081:1 4078:( 4075:O 4036:) 4033:1 4030:+ 4027:n 4024:( 4020:/ 4014:1 4011:+ 4005:) 4002:n 3999:( 3991:2 3979:2 3972:2 3969:+ 3963:) 3960:n 3957:( 3949:2 3921:1 3915:) 3912:n 3909:( 3901:2 3876:n 3872:/ 3868:) 3865:2 3856:) 3853:n 3850:( 3842:2 3826:1 3823:+ 3817:) 3814:n 3811:( 3803:2 3791:2 3787:( 3781:1 3778:+ 3772:) 3769:n 3766:( 3758:2 3724:) 3721:n 3718:( 3710:2 3679:1 3676:+ 3673:) 3670:n 3667:( 3659:2 3631:n 3605:1 3602:+ 3599:) 3596:n 3593:( 3585:2 3551:2 3493:1 3490:+ 3487:) 3484:n 3481:( 3473:2 3441:. 3409:] 3403:, 3397:, 3391:, 3385:, 3379:, 3373:, 3367:[ 3335:. 3323:1 3320:+ 3317:r 3296:r 3280:. 3268:1 3262:r 3242:r 3190:5 3128:T 3107:R 3101:n 3080:T 3059:T 3037:1 3031:R 3027:A 3006:T 3003:= 2998:1 2992:R 2988:A 2967:0 2961:R 2949:. 2937:1 2931:R 2918:. 2906:1 2903:+ 2900:m 2879:L 2858:T 2850:m 2846:A 2834:. 2822:m 2802:R 2782:T 2774:m 2770:A 2758:. 2744:2 2740:R 2737:+ 2734:L 2709:2 2705:R 2702:+ 2699:L 2672:m 2649:R 2643:L 2632:. 2620:n 2600:R 2580:0 2560:L 2499:T 2479:T 2455:L 2435:T 2415:T 2393:L 2389:A 2368:T 2365:= 2360:L 2356:A 2335:n 2329:L 2317:. 2305:L 2292:. 2280:m 2259:R 2238:T 2230:m 2226:A 2214:. 2202:1 2199:+ 2196:m 2176:L 2156:T 2148:m 2144:A 2132:. 2118:2 2114:R 2111:+ 2108:L 2083:2 2079:R 2076:+ 2073:L 2046:m 2023:R 2017:L 2006:. 1994:n 1974:R 1954:0 1934:L 1901:] 1898:7 1895:, 1892:6 1889:, 1886:5 1883:, 1880:4 1877:, 1874:4 1871:, 1868:4 1865:, 1862:2 1859:, 1856:1 1853:[ 1833:4 1813:] 1810:7 1807:, 1804:6 1801:, 1798:5 1795:, 1792:4 1789:, 1786:4 1783:, 1780:3 1777:, 1774:2 1771:, 1768:1 1765:[ 1684:L 1664:T 1661:= 1656:L 1652:A 1631:R 1628:= 1625:L 1612:. 1600:m 1580:L 1560:T 1552:m 1548:A 1536:. 1524:1 1518:m 1498:R 1478:T 1470:m 1466:A 1454:. 1440:2 1436:R 1433:+ 1430:L 1405:2 1401:R 1398:+ 1395:L 1368:m 1345:R 1339:L 1328:. 1316:1 1310:n 1290:R 1270:0 1250:L 1220:R 1217:= 1214:L 1194:T 1174:m 1144:2 1140:R 1137:+ 1134:L 1034:R 1014:L 1002:. 990:m 970:T 967:= 962:m 958:A 934:1 928:m 908:R 888:T 880:m 876:A 852:1 849:+ 846:m 826:L 806:T 798:m 794:A 782:. 768:2 764:R 761:+ 758:L 733:2 729:R 726:+ 723:L 696:m 673:R 667:L 656:. 644:1 638:n 618:R 598:0 578:L 554:A 534:T 510:T 488:1 482:n 478:A 463:2 459:A 450:1 446:A 437:0 433:A 410:1 404:n 400:A 396:, 390:, 385:2 381:A 377:, 372:1 368:A 364:, 359:0 355:A 331:n 311:A 239:n 219:) 216:n 207:( 204:O 140:O 124:) 122:n 118:O 100:O 84:) 82:n 78:O 23:.

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index