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.

Mentioned in ?

References in periodicals archive ?

Asymptotic distribution of two-protected nodes in random binary search trees.

On the number of vertices of each rank in k-phylogenetic trees

After calculating the bidding value it will create a binary search tree based on the binary search tree algorithm.

A novel framework for efficient bidding based scheduling in virtualized clouds

There are four reasonable, simple search models to consider, all based on doing a binary search on C and a sequential search on P.

How often should you clean your room?

The modern graphics processing units also provide random write access to memory, which can be used to replace the binary search phase.

Solutions for optimizing the stream compaction algorithmic function using the compute unified device architecture

The concept map for Binary Search Trees is presented in figure 1.

Expanding mental outlook with the help of concept maps

In digital land, a binary search is used to test many parameters that are not directly measurable, such as setup and hold time.

Testing low-pass filters with digital pins: binary search, a decrease-and-conquer approach, plays an important role in testing today's low-pass filters

Additional Key Words and Phrases: Binary Search on Levels, controlled prefix expansion, expanded tries, Internet address lookup, longest-prefix match, multibit tries, router performance

Fast Address Lookups Using Controlled Prefix Expansion

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).

Randomized Binary Search Trees

The balancing criterion of Gerasch's algorithm is that the binary search tree must always remain nearly complete.

Technical correspondence: on Gerasch's insertion algorithm

From a binary search tree T, one can construct bijectively two labelled forests of ordered trees: the final forest [F.

Two bijections on Tamari Intervals

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.

Digital search trees with m trees: level polynomials and insertion costs

Recursive algorithms are most often employed for various kinds of binary search.

Acceleration of recursive data sorting over tree-based structures/Pasikartojanciu duomenu rusiavimo paspartinimas duomenu masyvuose