binary search


Also found in: Dictionary, Thesaurus, Medical.

binary search

[′bīn·ə·rē ′sərch]
(computer science)
A dichotomizing search in which the set of items to be searched is divided at each step into two equal, or nearly equal, parts. Also known as binary chop.

binary search

(algorithm)
A search algorithm which repeatedly divides an ordered search space in half according to how the required (key) value compares with the middle element.

The following pseudo-C routine performs a binary search return the index of the element of vector "thing[first..last]" equal to "target":

if (target < thing[first] || target > thing[last]) return NOT_FOUND; while (first < last) mid = if (target == thing[last]) return last; return NOT_FOUND;

binary search

A technique for quickly locating an item in a sequential list. The desired key is compared to the data in the middle of a sequential index or in the middle of a sequential file. The half that contains the data is then compared in the middle, and so on, either until the key is located or a small enough group is isolated to be sequentially searched. See binary.
References in periodicals archive ?
Asymptotic distribution of two-protected nodes in random binary search trees.
After calculating the bidding value it will create a binary search tree based on the binary search tree algorithm.
There are four reasonable, simple search models to consider, all based on doing a binary search on C and a sequential search on P.
The modern graphics processing units also provide random write access to memory, which can be used to replace the binary search phase.
The concept map for Binary Search Trees is presented in figure 1.
In digital land, a binary search is used to test many parameters that are not directly measurable, such as setup and hold time.
Additional Key Words and Phrases: Binary Search on Levels, controlled prefix expansion, expanded tries, Internet address lookup, longest-prefix match, multibit tries, router performance
For random binary search trees, the expected performance of a search, whether successful or not, and that of update operations is O(log n) [Knuth 1973; Mahmoud 1992; Sedgewick and Flajolet 1996], with small hidden constant factors involved (here and unless otherwise stated, n denotes the number of items in the tree or size of the tree).
The balancing criterion of Gerasch's algorithm is that the binary search tree must always remain nearly complete.
From a binary search tree T, one can construct bijectively two labelled forests of ordered trees: the final forest [F.
A DST is constructed like a binary search tree, but the decision to go down to the left or right is done according to the representation of the key as a binary string of bits.