Binary search algorithm

binary searchbinarybinary chopBinary, or half interval searchesbinary_searchbsearchone-sided searchusing O(\log(b)) comparisons
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.wikipedia
207 Related Articles

Search algorithm

searchsearchingkeyword search
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
Binary, or half interval searches, repeatedly target the center of the search structure and divide the search space in half.

Time complexity

polynomial timelinear timeexponential time
Binary search runs in logarithmic time in the worst case, making O(\log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and \log is the logarithm.
Algorithms taking logarithmic time are commonly found in operations on binary trees or when using binary search.

Fractional cascading

cascaded
In particular, fractional cascading speeds up binary searches for the same value in multiple arrays.
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.

Binary search tree

binary search treesBSTsearch tree
The binary search tree and B-tree data structures are based on binary search.
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, on the basis of the comparison, to continue searching in the left or right subtrees.

Linear search

sequential searchlinear scanSequential
Binary search is faster than linear search except for small arrays.
Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists.

Binary logarithm

base-2 logarithmbase 2 logarithms\log_{2} x
In the worst case, binary search makes iterations of the comparison loop, where the notation denotes the floor function that yields the greatest integer less than or equal to the argument, and \log_2 is the binary logarithm.
In computer science, they count the number of steps needed for binary search and related algorithms.

Big O notation

Obig-O notationlittle-o notation
Binary search runs in logarithmic time in the worst case, making O(\log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and \log is the logarithm.

Exponential search

galloping" search
Exponential search extends binary search to unbounded lists.
There are numerous ways to implement this with the most common being to determine a range that the search key resides in and performing a binary search within that range.

Sorted array

In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
Elements within a sorted array are found using a binary search, in O(log n); thus sorted arrays are suited for cases when one needs to be able to look up elements quickly, e.g. as a set or multiset data structure.

B-tree

B*-treeB-treesB Tree
The binary search tree and B-tree data structures are based on binary search.
A binary search of a sorted table with N records, for example, can be done in roughly

Logarithm

logarithmsloglogarithmic function
Binary search runs in logarithmic time in the worst case, making O(\log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and \log is the logarithm.
For example, to find a number in a sorted list, the binary search algorithm checks the middle entry and proceeds with the half before or after the middle entry if the number is still not found.

Twenty Questions

20 Questionsanimal, vegetable or mineral20 spørsmål
The noisy binary search problem can be considered as a case of the Rényi-Ulam game, a variant of Twenty Questions where the answers may be wrong.
The process is analogous to a binary search algorithm in computer science or successive approximation ADC in analog-to-digital signal conversion.

Lookup table

lookuplook-up tabletable lookup
A lookup table containing the differences is computed beforehand.
An example of a "divide and conquer algorithm", binary search involves each element being found by determining which half of the table a match may be found in and repeating until either success or failure.

C (programming language)

CC programming languageC language
Pointers to functions are useful for passing functions as arguments to higher-order functions (such as qsort or bsearch) or as callbacks to be invoked by event handlers.

Standard Template Library

STLC++ STLC++ Standard Template Library
Searching algorithms like and use binary search and like sorting algorithms require that the type of data must implement comparison operator or custom comparator function must be specified; such comparison operator or comparator function must guarantee strict weak ordering.

C++

C++ programming languageC++98C with Classes
C++ programmers expect the latter on every major implementation of C++; it includes aggregate types (vectors, lists, maps, sets, queues, stacks, arrays, tuples), algorithms (find, for_each, binary_search, random_shuffle, etc.), input/output facilities (iostream, for reading from and writing to the console and files), filesystem library, localisation support, smart pointers for automatic memory management, regular expression support, multi-threading library, atomics support (allowing a variable to be read or written to by at most one thread at a time without any external synchronisation), time utilities (measurement, getting current time, etc.), a system for converting error reporting that doesn't use C++ exceptions into C++ exceptions, a random number generator and a slightly modified version of the C standard library (to make it comply with the C++ type system).

Computer science

computer scientistcomputer sciencescomputer scientists
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.

Best, worst and average case

worst caseworst-caseaverage case
Binary search runs in logarithmic time in the worst case, making O(\log n) comparisons, where n is the number of elements in the array, the O is Big O notation, and \log is the logarithm.

Data structure

data structuresstructurestructures
There are specialized data structures designed for fast searching, such as hash tables, that can be searched more efficiently than binary search.

Computational geometry

computational geometergeometric algorithmssearch space
Fractional cascading efficiently solves a number of search problems in computational geometry and in numerous other fields.

Record (computer science)

recordrecordsstruct
For implementing associative arrays, hash tables, a data structure that maps keys to records using a hash function, are generally faster than binary search on a sorted array of records.

Pseudocode

pseudo-codepseudo codepseudo
This iterative procedure keeps track of the search boundaries with the two variables L and R. The procedure may be expressed in pseudocode as follows, where the variable names and types remain the same as above, is the floor function, and refers to a specific value that conveys the failure of the search.

Hermann Bottenbruch

BottenbruchBottenbruch, Hermann
Hermann Bottenbruch published the first implementation to leave out this check in 1962.