Binary search algorithm

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

Binary search algorithm
Visualization of the binary search algorithm where 4 is the target value.
Class	Search algorithm
Data structure	Array
Worst case performance	O(log n)
Best case performance	O(1)
Average case performance	O(log n)
Worst case space complexity	O(1)

In computer science, binary search, also known as half-interval search^[1] or logarithmic search^[2], is a search algorithm that finds the position of a target value, whether alone or part of a record, within a sorted array.^[3]^[4] It works by comparing the target value to the middle element of the array; if they are not equal, the lower or upper half of the array is eliminated depending on the result and the search is repeated until the position of the target value is found.

With little extra space, binary search runs in at worst logarithmic time, making ${\textstyle O(\log n)}$ comparisons, where ${\textstyle n}$ is the number of elements in the array and ${\textstyle \log}$ is the binary logarithm.^[5] Although binary search runs efficiently, there exist other data structures, such as hash tables, that exhibit better performance for exact searches. Especially for implementing associative arrays, exact searches are enough for many applications. However, it is difficult or impossible to perform approximate search operations—important for some applications such as priority queues—on many of these data structures, such as finding the next-smallest, next-largest, and nearest element relative to an element, while binary search can perform such searches in logarithmic time or faster.

There are numerous variations of binary search that may run faster on some arrays or computers; one variation stores the midpoint and width of the search instead of its bounds. However, even the details for the basic binary search can lead to implementation pitfalls, particularly relating to calculating the midpoint and search bounds.

Algorithm

Binary search only works on sorted arrays. A binary search begins by comparing the middle element of the array with the target value. If the target value matches the middle element, its position in the array is returned. If the target value is less or more than the middle element, the search continues the lower or upper half of the array respectively with a new middle element, eliminating the other half from consideration.^[6] This method can be described recursively or iteratively.

Procedure

Given an array A of n elements with values or records A₀ ... A_n−1 and target value T, the following subroutine uses binary search to find the index of T in A.^[6]

Set L to 0 and R to n−1.
If L > R, the search terminates as unsuccessful. Set m (the position of the middle element) to the floor of (L + R) / 2.
If A_m = T, the search is done; return m.
If A_m < T, set L to m + 1 and go to step 2.
If A_m > T, set R to m - 1 and go to step 2.

This iterative procedure keeps track of the search boundaries via two variables; a recursive version would keep its boundaries in its recursive calls. Some implementations may place the comparison for equality at the end, resulting in a faster comparison loop but costing one more iteration on average.^[7]

Approximate matches

The above procedure only performs exact matches, finding the position of a target value. However, due to the ordered nature of sorted arrays, it is trivial to extend binary search to perform approximate matches. Particularly, binary search can be used to compute, relative to a element, its predecessor (next-smallest element), successor (next-largest element), and nearest neighbor. Range queries (the number of elements between two elements) can be performed with two binary searches.^[7]

Predecessor and successor queries are trivial with binary search: for any sorted array, once the position P of the target value in a sorted array A is computed using binary search, the predecessor is A_P−1 and the successor is A_P+1.^[8] The nearest neighbor of an element is either its predecessor or successor, whichever has the smallest difference from the element.
Range queries are also straightforward: once the positions of the two elements are known, the range is simply the difference between them.^[7]

Performance

A tree representing binary search

The performance of binary search can be analyzed by reducing the procedure to a binary comparison tree, where the root node is the middle element of the array; the middle element of the lower half is left of the root and the middle element of the upper half is right of the root. The rest of the tree is built in a similar fashion. This model represents binary search; starting from the root node, the left subtree is traversed if the target value is less than the node under consideration and vice versa, representing the successive elimination of elements.^[5]^[9]

The worst case is reached when the search reaches the deepest level of the tree; this is equivalent to a binary search where the element is found or the search is terminated only after the search has reduced to one element, and it is reached after ${\textstyle \lfloor \log n + 1 \rfloor}$ iterations (of the comparison loop), where the ${\textstyle \lfloor \rfloor}$ notation denotes the floor function that rounds its argument down to an integer.^[9] On average, assuming that each element is equally likely to be searched, by the time the search completes, there will be one layer of the tree remaining. This is equivalent to a binary search that has reduced to two elements, and it is reached after about ${\textstyle \log{n} - 1}$ iterations.^[5] In the best case, where the first middle element selected is equal to the target value, its position is returned after one iteration.^[10]

Each iteration of the binary search algorithm defined above makes two comparisons, checking if the middle element is equal to the target value in each iteration. A variation of the algorithm instead checks for equality at the very end of the search, eliminating one comparison from each iteration. This decreases the time taken per iteration very slightly on most computers, while guaranteeing that the search takes the maximum number of iterations, on average adding one iteration to the search. Because the comparison loop is performed only ${\textstyle \log n}$ times, for all but enormous ${\textstyle n}$ , the slight increase in comparison loop efficiency does not compensate for the extra iteration. Knuth 1998 gives a value of ${\textstyle 2^{66}}$ (about 73 quintillion) elements for this variation to be faster.^[11]

When multiple binary searches are to be performed for the same key in related lists, fractional cascading can be used to speed up successive searches after the first one.

Binary search versus other schemes

Hash tables

For implementing associative arrays, hash tables, a data structure that maps keys to records using a hash function, are generally faster than binary search on a sorted array of records;^[12] most implementations require only amortized constant time on average.^[a]^[14] 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 key is not present in any record.^[15]

Binary search is ideal for such matches, performing them in logarithmic time. In addition, all operations possible on a sorted array can be performed—such as finding the smallest and largest key and performing range searches.^[16]

Binary search trees

A binary search tree is a binary tree data structure that works based on the principle of binary search: the records of the tree are arranged in sorted order, and traversal of the tree is performed using a binary search-like algorithm. The main advantage of binary search trees over binary search is that it allows for significantly faster insertion and deletion (proportional to ${\textstyle \log{n}}$ instead of ${\textstyle n}$ for sorted arrays), while retaining the ability to perform all the operations possible on a sorted array.

However, binary search is usually more efficient for searching as binary search trees will most likely be imbalanced, resulting in slightly worse performance than binary search. Although unlikely, the tree may be severely imbalanced with few internal nodes with two children, resulting in the average and worst-case search time approaching ${\textstyle n}$ comparisons.^[b] Balanced binary search trees attempt to balance their own nodes, improving the time performance of searches, but at a cost to insertion and deletion time. More significantly, if the sorted array of records is required anyway, binary search can be faster than binary search trees, as it takes linear time in the worst case and extra space to traverse a binary search tree and fetch the records in sorted order.^[18]^[19]

Linear search

Linear search is a simple search algorithm that checks every record until it finds the target value. Binary search is faster than linear search for non-trivial sorted arrays.^[20] If the array must first be sorted, that cost must be amortized over any searches. Sorting the array also enables efficient approximate matches and other operations.

Other data structures

There exist data structures that may beat binary search in some cases for both searching and other operations available for sorted arrays. For example, searches, approximate matches, and a subset of the operations available to sorted arrays can be performed much more efficiently than binary search on specialized data structures such as van Emde Boas trees, fusion trees, tries, and bit arrays. However, while these operations can always be done at least efficiently on a sorted array regardless of the keys, such data structures are usually only faster because they exploit 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 do not have that attribute.^[16]

Variations

Uniform binary search

A variation of the algorithm forgoes the lower and upper pointers or variables, instead storing the index of the middle element and the width of the search; i.e., the number of elements around the middle element that has not been eliminated yet. Each step reduces the width by about half. This algorithm is called the uniform binary search because the difference between the indices of middle elements and the preceding middle elements chosen remains constant between searches of arrays of the same length.^[21]

A lookup table containing the widths at each step of the search can be calculated in advance, eliminating the need to keep track of a middle element as it can be calculated using the table.^[22]

Fibonaccian search

Fibonaccian search exploits the Fibonacci numbers to eliminate division from the algorithm, instead using addition and subtraction; this is faster on some computers. It works like the uniform binary search, except it bases the width of the search on the Fibonacci numbers. This search is theoretically less efficient in the worst case than traditional uniform binary search, although more efficient in the average case.^[23]

Exponential search

Main article: Exponential search

Exponential search is an algorithm for searching primarily in infinite lists, but it can be applied to select the upper bound for binary search. It starts by finding the first element in index ${\textstyle 2^j}$ that exceeds the target value, where ${\textstyle j}$ starts at zero and increments by one per iteration. Afterwards, it sets that index as the upper bound, and switches to binary search. This is efficient if the target value is located near the beginning of the array, with ${\textstyle \lfloor \log{x} + 1\rfloor}$ iterations of the exponential search and at most ${\textstyle \lfloor \log{n} \rfloor}$ iterations of the binary search, where ${\textstyle x}$ is the position of the target value.^[24]

Interpolation search

Main article: Interpolation search

Instead of merely calculating the midpoint, interpolation search attempts to calculate the position of the target value, taking into account the lowest and highest elements in the array and the length of the array. It works on the basis that the midpoint is not the best guess in many cases; for example, if the target value is close to the highest element in the array, it is likely to be located near the end of the array. It is theoretically efficient for arrays whose elements successively increase by a constant or close to constant amount, making about ${\textstyle \log{\log{n}}}$ comparisons in the average case.

In practice, interpolation search is faster than binary search only when the search space of the array is large, as the time difference between interpolation and binary search does not compensate for the extra computation required for small arrays. It is most successful as a precursor to binary search, eliminating elements while the search space is large and switching to binary search afterwards.^[25]

Equality test at end of program

Binary search is dichotomic, meaning that there are two choices to be made per step, but only after the target element is compared with the middle element. This comparison can be moved to the end of the program, after the search is reduced to one element. This approach allows the comparison loop to save on average one comparison; however, in practice, this is slower than traditional binary search for all but enormous ${\textstyle n}$ . Its main advantage is that if the elements are not unique, it is guaranteed to return the largest index where the element is equal to the target value. The traditional version would return the first match it found.^[26]^[11]

History

The first example of a list of numbers sorted to allow for faster searching dates back to the Babylonian Inakibit-Anu tablet from c. 200 BCE; it contained a sorted list of about 500 sexagesimal numbers and their reciprocals. The first mention of binary search was made in 1946 by John Mauchly while giving one of the Moore School Lectures, the first ever course regarding any computer-related topic.^[26]

No binary search algorithm was published that worked for arrays not of length ${\textstyle 2^n - 1}$ for any natural number ${\textstyle n}$ until 1960, when Derrick Henry Lehmer published, along with the Lehmer code, a binary search algorithm that worked on all arrays.^[27] In 1962, Hermann Bottenbruch presented an ALGOL 60 implementation of binary search that placed the comparison for equality at the end, increasing the number of steps by one, but reducing to one the number of comparisons per step, as well as ensuring that the position of the rightmost element is returned if the target value is duplicated in the array.^[28] The uniform binary search was presented to Donald Knuth in 1971 by A. K. Chandra of Stanford University and published in Knuth's The Art of Computer Programming.^[26]

Implementation issues

Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky… — Donald Knuth^[2]

When Jon Bentley assigned it as a problem in a course for professional programmers, he found that an astounding ninety percent failed to code a binary search correctly after several hours of working on it,^[29] and another study shows that accurate code for it is only found in five out of twenty textbooks.^[30] Furthermore, Bentley's own implementation of binary search, published in his 1986 book Programming Pearls, contained an overflow error that remained undetected for over twenty years.^[31]

Arithmetic

In a practical implementation, the variables used to represent the indices will often be of finite size, hence only capable of representing a finite range of values. For example, 32-bit unsigned integers can only hold values from 0 to 4294967295. 32-bit signed integers can only hold values from -2147483648 to 2147483647. If the binary search algorithm is to operate on large arrays, this has two implications:^[32]

The values first − 1 and last + 1 must both be representable within the finite bounds of the chosen integer type . Therefore, continuing the 32-bit unsigned example, the largest value that last may take is +4294967294, not +4294967295.
If the midpoint of the span is calculated as p := (L + R)/2, then the value (L + R) will exceed the number range if last is greater than (for unsigned) 4294967295/2 or (for signed) 2147483647/2 and the search wanders toward the upper end of the search space. This can be avoided by performing the calculation as p := (R - L)/2 + L.

Language support

Many standard libraries provide a way to do a binary search:

C provides the function bsearch() in its standard library, which is typically implemented via binary search (although the official standard does not require it so).^[33]
C++'s STL provides the functions binary_search(), lower_bound(), upper_bound() and equal_range().^[34]
Java offers a set of overloaded binarySearch() static methods in the classes Arrays and Collections in the standard java.util package for performing binary searches on Java arrays and on Lists, respectively.
Microsoft's .NET Framework 2.0 offers static generic versions of the binary search algorithm in its collection base classes. An example would be System.Array's method BinarySearch<T>(T[] array, T value).
Python provides the bisect module.
COBOL can perform binary search on internal tables using the SEARCH ALL statement.
Perl can perform a generic binary search using the CPAN module List::BinarySearch.^[35]
Ruby's Array class has included a bsearch method since version 2.0.0.
Go's sort standard library package contains the functions Search, SearchInts, SearchFloat64s, and SearchStrings, which implement general binary search, as well as specific implementations for searching slices of integers, floating-point numbers, and strings, respectively.^[36]
For Objective-C, the Cocoa framework provides the NSArray -indexOfObject:inSortedRange:options:usingComparator: method in Mac OS X 10.6+. Apple's Core Foundation C framework also contains a CFArrayBSearchValues() function.

Notes

^ It is possible to perform hashing in guaranteed constant time.^[13]
^ This occurs when the records are inserted in sorted or near-sorted order or in an alternating lowest-highest record pattern.^[17]

References

^ Willams, Jr., Louis F. (1975). "A modification to the half-interval search (binary search) method". ACM-SE 14: 96–101. doi:10.1145/503561.503582.
^ ^a ^b Knuth 1998, §6.2.1, "Binary search".
^ Cormen et al. 2009, p. 39.
^ Weisstein, Eric W., "Binary Search", MathWorld.
^ ^a ^b ^c Flores, Ivan; Madpis, George (1971). "Average binary search length for dense ordered lists". CACM 14 (9): 602–603. doi:10.1145/362663.362752.
^ ^a ^b Knuth 1998, §6.2.1, "Algorithm B".
^ ^a ^b ^c Sedgewick & Wayne 2011, §3.1, "Elementary Symbol Tables".
^ Goldman & Goldman 2008, pp. 361-362.
^ ^a ^b Knuth 1998, §6.2.1, "Further analysis of binary search".
^ Chang 2003, p. 169.
^ ^a ^b Knuth 1998, §6.2.1, "Exercise 23".
^ Knuth 1998, §6.4, "Hashing".
^ Knuth 1998, §6.4, "History".
^ Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (August 1994). "Dynamic Perfect Hashing: Upper and Lower Bounds". SIAM Journal on Computing 23 (4): 738–761. doi:10.1137/S0097539791194094.
^ Morin, Pat. "Hash Tables" (PDF). p. 1. Retrieved 28 March 2016.
^ ^a ^b Beame, Paul; Fich, Faith E. (2001). "Optimal Bounds for the Predecessor Problem and Related Problems". Journal of Computer and System Sciences 65 (1): 38–72. doi:10.1006/jcss.2002.1822.
^ Knuth 1998, §6.2.2, "But what about the worst case?".
^ Knuth 1997, §2.3.1, "Program S".
^ Sedgewick & Wayne 2011, §3.2, "Proposition" under "Order-based methods and deletion".
^ Knuth 1998, §6.2.1, "Searching an ordered table".
^ Knuth 1998, §6.2.1, "An important variation".
^ Knuth 1998, §6.2.1, "Algorithm U".
^ Knuth 1998, §6.2.1, "Fibonaccian search".
^ Moffat & Turpin 2002, p. 33.
^ Knuth 1998, §6.2.1, "Interpolation search".
^ ^a ^b ^c Knuth 1998, §6.2.1, "History and bibliography".
^ Lehmer, Derrick (1960). "Teaching combinatorial tricks to a computer". Proceedings of Symposia in Applied Mathematics 10: 180–181.
^ Bottenbruch, Hermann (1962). "Structure and Use of ALGOL 60". Journal of the ACM 9 (2): 214.
^ Bentley 2000, p. 341.
^ Pattis, Richard E. (1988). "Textbook errors in binary searching". SIGCSE Bulletin 20: 190–194. doi:10.1145/52965.53012.
^ Bloch, Joshua (June 2, 2006) [Updated 17 Feb 2008]. "Extra, Extra – Read All About It: Nearly All Binary Searches and Mergesorts are Broken". Google Research Blog.
^ Ruggieri, Salvatore (2003). "On computing the semi-sum of two integers" (PDF). Information Processing Letters 87 (2): 67–71. doi:10.1016/S0020-0190(03)00263-1.
^ "bsearch - binary search a sorted table". The Open Group Base Specifications (7th ed.). The Open Group. 2013. Retrieved 28 March 2016.
^ Stroustrup 2013, §32.6.1, "Binary Search".
^ "List::BinarySearch". CPAN.
^ "Package sort". The Go Programming Language.

Bibliography

Knuth, Donald (1998). Sorting and Searching. The Art of Computer Programming 3 (2nd ed.). Reading, MA: Addison-Wesley Professional.
Knuth, Donald (1997). Fundamental Algorithms. The Art of Computer Programming 1 (3rd ed.). Reading, MA: Addison-Wesley Professional.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
Bentley, Jon (2000) [1986]. Programming Pearls (2nd ed.). Addison-Wesley. p. 341. ISBN 0-201-65788-0.
Chang, Shi-Kuo (2003). Data Structures and Algorithms. Software Engineering and Knowledge Engineering 13 (Singapore: World Scientific). p. 169. ISBN 978-9812383488.
Goldman, Sally A.; Goldman, Kenneth J. (2008). A Practical Guide to Data Structures and Algorithms using Java. Boca Raton: CRC Press. pp. 361–362. ISBN 9781584884552.
Moffat, Alistair; Turpin, Andrew (2002). Compression and Coding Algorithms. Hamburg, Germany: Kluwer Academic Publishers. doi:10.1007/978-1-4615-0935-6. ISBN 978-0-7923-7668-2.
Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-57351-3.
Stroustrup, Bjarne (2013). The C++ Programming Language (4th ed.). Upper Saddle River, NJ: Addison-Wesley Professional. ISBN 978-0-321-56384-2.

External links

fonte: https://web.archive.org/web/20160415100143/https://en.wikipedia.org/wiki/Binary_search_algorithm

Conheça Walt Disney World