Binary Search

Binary search compares against the middle of a sorted array and halves the range each time, locating a target in O(log n); it is the foundational efficient search algorithm.

Purpose

To locate elements efficiently in sorted data, applying logarithmic complexity to search.

Mechanism

Maintain the interval [lo, hi] with mid=(lo+hi)/2; compare mid with the target: return on equality, search the right half if smaller, the left half if larger. The interval halves each step, giving O(log n). Sortedness is a prerequisite. Variants: lower bound, upper bound, insertion point.

Use cases

Sorted array lookup
Database B+ tree indexes
Version control bisect
Finding function zeros (bisection)

Examples

Input
```
Search 5 in [1,3,5,7,9]
```
Output
```
Index 2
```
2 comparisons

Common errors

lo+hi integer overflow: Use lo+(hi-lo)/2

Related terms

Sorting Algorithm

Sorting algorithms arrange elements in order—quicksort, merge sort, and heapsort are common—with complexity ranging from O(n log n) to O(n²).

Big O notation describes the asymptotic upper bound of a function, used to analyze algorithm time/space complexity while ignoring constants and lower-order terms.

A hash table maps keys to a bucket array via a hash function, providing average O(1) lookup/insert/delete; it is among the most used data structures.

References