In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to practical disciplines (includi ...
, binary search, also known as half-interval search,
logarithmic search, or binary chop, is a
search algorithm
In computer science, a search algorithm is an algorithm designed to solve a search problem. Search algorithms work to retrieve information stored within particular data structure, or calculated in the search space of a problem domain, with eith ...
that finds the position of a target value within a
sorted array
A sorted array is an array data structure in which each element is sorted in numerical, alphabetical, or some other order, and placed at equally spaced addresses in computer memory. It is typically used in computer science to implement static l ...
. Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.
Binary search runs in
logarithmic time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
in the
worst case
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
, making
comparisons, where
is the number of elements in the array.
Binary search is faster than
linear search except for small arrays. However, the array must be sorted first to be able to apply binary search. There are specialized
data structures
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, a ...
designed for fast searching, such as
hash tables
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', ...
, that can be searched more efficiently than binary search. However, binary search can be used to solve a wider range of problems, such as finding the next-smallest or next-largest element in the array relative to the target even if it is absent from the array.
There are numerous variations of binary search. In particular,
fractional cascading In computer science, fractional cascading is a technique to speed up a sequence of binary searches for the same value in a sequence of related data structures. The first binary search in the sequence takes a logarithmic amount of time, as is standar ...
speeds up binary searches for the same value in multiple arrays. Fractional cascading efficiently solves a number of search problems in
computational geometry and in numerous other fields.
Exponential search
In computer science, an exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. There are num ...
extends binary search to unbounded lists. The
binary search tree
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...
and
B-tree
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for ...
data structures are based on binary search.
Algorithm
Binary search works on sorted arrays. Binary search begins by comparing an element in the middle of the array with the target value. If the target value matches the element, its position in the array is returned. If the target value is less than the element, the search continues in the lower half of the array. If the target value is greater than the element, the search continues in the upper half of the array. By doing this, the algorithm eliminates the half in which the target value cannot lie in each iteration.
Procedure
Given an array
of
elements with values or
records
A record, recording or records may refer to:
An item or collection of data Computing
* Record (computer science), a data structure
** Record, or row (database), a set of fields in a database related to one entity
** Boot sector or boot record, r ...
sorted such that
, and target value
, the following
subroutine uses binary search to find the index of
in
.
# Set
to
and
to
.
# If
, the search terminates as unsuccessful.
# Set
(the position of the middle element) to the
floor of
, which is the greatest integer less than or equal to
.
# If
, set
to
and go to step 2.
# If
, set
to
and go to step 2.
# Now
, the search is done; return
.
This iterative procedure keeps track of the search boundaries with the two variables
and
. The procedure may be expressed in
pseudocode as follows, where the variable names and types remain the same as above,
floor
is the
floor function
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...
, and
unsuccessful
refers to a specific value that conveys the failure of the search.
function binary_search(A, n, T) is
L := 0
R := n − 1
while L ≤ R do
m := floor((L + R) / 2)
if A
< T then
L := m + 1
else if A
> T then
R := m − 1
else:
return m
return unsuccessful
Alternatively, the algorithm may take the
ceiling of
. This may change the result if the target value appears more than once in the array.
Alternative procedure
In the above procedure, the algorithm checks whether the middle element (
) is equal to the target (
) in every iteration. Some implementations leave out this check during each iteration. The algorithm would perform this check only when one element is left (when
). This results in a faster comparison loop, as one comparison is eliminated per iteration, while it requires only one more iteration on average.
[ Procedure is described at p. 214 (§43), titled "Program for Binary Search".]
Hermann Bottenbruch
Hermann Bottenbruch (14 September 1928 – 20 May 2019) was a German mathematician and computer scientist.
Bottenbruch grew up in . Toward the end of World War II, he served as a . In 1947, he began the study of mathematics at the where he grad ...
published the first implementation to leave out this check in 1962.
# Set
to
and
to
.
# While
,
## Set
(the position of the middle element) to the
ceiling of
, which is the least integer greater than or equal to
.
## If
, set
to
.
## Else,
; set
to
.
# Now
, the search is done. If
, return
. Otherwise, the search terminates as unsuccessful.
Where
ceil
is the ceiling function, the pseudocode for this version is:
function binary_search_alternative(A, n, T) is
L := 0
R := n − 1
while L != R do
m := ceil((L + R) / 2)
if A
> T then
R := m − 1
else:
L := m
if A
= T then
return L
return unsuccessful
Duplicate elements
The procedure may return any index whose element is equal to the target value, even if there are duplicate elements in the array. For example, if the array to be searched was