Binary search algorithm

related topics
{math, number, function}
{rate, high, increase}
{system, computer, user}
{work, book, publish}
{math, energy, light}
{city, population, household}
{law, state, case}
{game, team, player}
{theory, work, human}

In computer science, a binary search or half-interval search algorithm locates the position of an item in a sorted array.[1][2] Binary search works by comparing an input value to the middle element of the array. The comparison determines whether the element equals the input, less than the input or greater. When the element being compared to equals the input the search stops and typically returns the position of the element. If the element is not equal to the input then a comparison is made to determine whether the input is less than or greater than the element. Depending on which it is the algorithm then starts over but only searching the top or bottom subset of the array's elements. If the input is not located within the array the algorithm will usually output a unique value indicating this. Binary search algorithms typically halve the number of items to check with each successive iteration, thus locating the given item (or determining its absence) in logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.

Contents

Full article ▸

related documents
Bernoulli number
Field (mathematics)
Distribution (mathematics)
Computer numbering formats
Fibonacci number
Mandelbrot set
Linked list
Trigonometric functions
Spinor
System of linear equations
Quadratic reciprocity
History of mathematics
Laplace transform
Prolog
C++
Relational model
Combinatory logic
Linear programming
Big O notation
Turing machine
Wikipedia:Free On-line Dictionary of Computing/R - S
Number
Forth (programming language)
Red-black tree
Derivative
Banach–Tarski paradox
Complex number
Formal power series
Lebesgue integration
Radix sort