Binary search algorithm

for performing binary searches on Java arrays and Lists, respectively. They must be arrays of primitives, or the arrays or Lists must be of a type that implements the Comparable interface, or you must specify a custom Comparator object. 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 [] array, T value). Python provides the bisect module. COBOL can perform binary search on internal tables using the SEARCH ALL statement.

ee also

* Index (information technology) Very fast 'lookup' using an index to directly select an entry
* Branch tables Alternative indexed 'lookup' technique for decision making
* Self-balancing binary search tree
* Run-time analysis, illustrating binary search technique on machines of differing speeds

References

* Donald Knuth. "The Art of Computer Programming", Volume 3: "Sorting and Searching", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.1: Searching an Ordered Table, pp.409–426.
* Kruse, Robert L.: "Data Structures and Program Design in C++", Prentice-Hall, 1999, ISBN 0-13-768995-0, page 280.
* Netty van Gasteren, Wim Feijen. " [http://www.mathmeth.com/wf/files/wf2xx/wf214.pdf The Binary Search Revisited] ", AvG127/WF214, 1995. (investigates the foundations of the Binary Search, debunking the myth that it applies only to sorted arrays)

External links

* [http://www.nist.gov/dads/HTML/binarySearch.html NIST Dictionary of Algorithms and Data Structures: binary search]
* [http://www.sparknotes.com/cs/searching/binarysearch/ Sparknotes: Binary search] . Simplified overview of binary search.
* [http://blogs.netindonesia.net/adrian/articles/6288.aspx Binary Search Implementation in Visual Basic .NET (partially in English)]
* [http://msdn2.microsoft.com/en-us/library/2cy9f6wb.aspx msdn2.microsoft.com/en-us/library/2cy9f6wb.aspx] .NET Framework Class Library Array.BinarySearch Generic Method (T [] , T)
* [http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html Google Research: Nearly All Binary Searches and Mergesorts are Broken] .
* [http://en.literateprograms.org/Category:Binary_search Implementations of binary search on LiteratePrograms] .
* [http://www.datastructures.info/what-is-a-binary-seach-algorithm-and-how-does-it-work/ Explained and commented Binary search algorithm in C++]
* [http://www.paked.net/subject_pages/computer_science/prog1.htm Binary Search using C++ ]