Binary Search
An algorithm that locates a target in a sorted array in logarithmic time by repeatedly halving the search interval.
Binary search finds the position of a target value inside a sorted array in O(log n) time. Instead of inspecting every element, it compares the target with the middle element, then discards the half of the array that cannot contain the target. Each comparison halves the remaining search space, so an array of one million elements needs at most about twenty comparisons.
The algorithm maintains two boundaries, low and high, that enclose the region that may still contain the target. It computes mid, compares array[mid] with the target, and moves either the low or the high boundary past mid depending on the result. The loop ends when the target is found or when the region becomes empty, which means the target is absent.
function binary_search(a, target):
low = 0
high = len(a) - 1
while low <= high:
mid = low + (high - low) / 2
if a[mid] == target: return mid
if a[mid] < target: low = mid + 1
else: high = mid - 1
return -1
Two requirements matter. The input must be sorted according to the same ordering used by the comparisons, and the container must support random access so that the middle element can be read in constant time. Linked lists are a poor fit because finding the middle requires traversal, which degrades the algorithm to O(n).
Variants such as lower_bound and upper_bound locate the first or last position where a value could be inserted without breaking the sort order; these are the building blocks of many standard-library functions, including C++ std::lower_bound, Python's bisect module, and Java's Arrays.binarySearch. Database engines use the same halving idea inside B-tree indexes to locate keys, and programmers use it to bisect failing test cases when debugging. The logarithmic growth of its cost is a standard example in Big O notation.
Tags
algorithms data structures searching