binary search

(algorithm)

Definition: Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Generalization (I am a kind of ...)
dichotomic search.

Aggregate parent (I am a part of or used in ...)
binary insertion sort, ideal merge, suffix array.

Aggregate child (... is a part of or used in me.)
divide and conquer.

Note: Run time is O(ln n).

Finding the middle is often coded as
mid = (high + low)/2;
This overflows if high and low are close to the largest expressible integer. The following gives the same result and never overflows, if high and low are non-negative.
mid = low + (high - low)/2;
Thanks to Colin D. Wright, 1 June 2005.

The implementation of search in C uses 0-based indexing.

Author: PEB

Implementation

Mukundan's animation (Java). search (C) where indexes are 0 to n, inclusive. That is, n is the highest index of the 0-based array, and possible key indexes, k, are low < k <= high in the loop. (Scheme), Worst-case behavior annotated for real time (WOOP/ADA), including bibliography.

More information

explanation

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 14 May 2007.
HTML page formatted Mon May 14 10:01:55 2007.

Cite this as:
Paul E. Black, "binary search", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 14 May 2007. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/binarySearch.html