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++ ]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Search algorithm — In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer… …   Wikipedia

  • Binary search tree — In computer science, a binary search tree (BST) is a binary tree data structurewhich has the following properties: *each node (item in the tree) has a value; *a total order (linear order) is defined on these values; *the left subtree of a node… …   Wikipedia

  • Uniform binary search — is an optimization of the classic binary search algorithm invented by Donald Knuth and given in Knuth s The Art of Computer Programming . It uses a lookup table to update a single array index, rather than taking the midpoint of an upper and a… …   Wikipedia

  • Self-balancing binary search tree — In computer science, a self balancing binary search tree or height balanced binary search tree is a binary search tree that attempts to keep its height , or the number of levels of nodes beneath the root, as small as possible at all times,… …   Wikipedia

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Binary logarithm — NOTOC In mathematics, the binary logarithm (log2 n ) is the logarithm for base 2. It is the inverse function of n mapsto 2^n. The binary logarithm is often used in computer science and information theory (where it is frequently written lg n , or… …   Wikipedia

  • Algorithm examples — This article Algorithm examples supplements Algorithm and Algorithm characterizations. = An example: Algorithm specification of addition m+n =Choice of machine model:This problem has not been resolved by the mathematics community. There is no… …   Wikipedia

  • Divide and conquer algorithm — In computer science, divide and conquer (D C) is an important algorithm design paradigm based on multi branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub problems of the same (or… …   Wikipedia

  • Interpolation search — is an algorithm for searching for a given key value in an indexed array that has been ordered by the values of the key. It parallels how humans search through a telephone book for a particular name, the key value by which the book s entries are… …   Wikipedia

  • Index (search engine) — Search engine indexing collects, parses, and stores data to facilitate fast and accurate information retrieval. Index design incorporates interdisciplinary concepts from linguistics, cognitive psychology, mathematics, informatics, physics, and… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”