# 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**

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

### Subroutine

**functionfunctionssubroutines**

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

### Nearest neighbor search

**nearest neighbornearest neighbor analysisnearest neighbors**