Binary search is an algorithm that locates a target value in a sorted array by repeatedly halving the search space — comparing the target with the middle element and discarding the half that cannot contain the target — achieving O(log n) worst-case time with O(1) space.
Binary search finds a value in a sorted array by always looking at the middle element — if it's too big, discard the right half; if too small, discard the left half — halving the search space with each step.
How it works
Binary search requires a sorted array. Maintain two pointers: lo (left boundary) and hi (right boundary). Repeat: compute the midpoint mid = (lo + hi) / 2. If arr[mid] equals the target, return mid. If arr[mid] < target, search the right half (set lo = mid + 1). If arr[mid] > target, search the left half (set hi = mid - 1). Stop when lo > hi — target not found.
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2 # avoids integer overflow vs. (lo+hi)//2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1 # target in right half
else:
hi = mid - 1 # target in left half
return -1 # not found
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print(binary_search(arr, 7)) # 3 (index)
print(binary_search(arr, 6)) # -1 (not found)public static int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // safe midpoint
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}Complexity
| Case | Time | Space | Notes |
|---|---|---|---|
| Best | O(1) | O(1) | Target is the middle element |
| Average | O(log n) | O(1) | |
| Worst | O(log n) | O(1) | Target not present or at boundary |
Why O(log n)?
Each step halves the search space. Starting with n elements: after 1 step ≈ n/2, after 2 steps ≈ n/4, … after k steps ≈ n/2k. The algorithm stops when the space reaches 1: n/2k = 1, so k = log₂n. At most ⌌log₂n⌍ + 1 iterations — O(log n). For n = 1,000,000: at most 20 iterations.
The critical requirement: sorted input
Binary search only works on sorted data. Applying it to an unsorted array gives incorrect results — the algorithm assumes that discarding a half is valid because all elements in the discarded half are either all larger or all smaller than the target. Sorting costs O(n log n); if you only need to search once, use linear search O(n). Binary search becomes worthwhile when you search many times on the same data.
The off-by-one problem
Binary search is famously easy to get wrong. The midpoint calculation (lo + hi) / 2 overflows a 32-bit integer when lo + hi > 231−1. The safe version: lo + (hi - lo) / 2. The loop condition lo <= hi vs. lo < hi determines whether a single-element array is searched. Boundary updates lo = mid + 1 vs. lo = mid determine whether infinite loops are possible. Knuth TAOCP Vol. 3 §6.2.1 notes that it took 16 years after binary search's first publication before a bug-free implementation appeared in print.
Variants: lower bound and upper bound
Lower bound: find the first index i where arr[i] ≥ target. Upper bound: find the first index i where arr[i] > target. These are used to find the range of all occurrences of a value in a sorted array. Python's bisect module provides bisect_left (lower bound) and bisect_right (upper bound).
import bisect
arr = [1, 3, 5, 5, 5, 7, 9]
target = 5
lo = bisect.bisect_left(arr, target) # 2 — first occurrence
hi = bisect.bisect_right(arr, target) # 5 — one past last occurrence
print(f"Found {hi - lo} occurrences at indices {lo}..{hi-1}") # 3 occurrences at 2..4Generalisation: binary search on the answer
Binary search is not just for arrays — it applies to any monotone function. If f(x) is monotone (increasing or decreasing), you can binary search for the value of x where f(x) equals some target. "Find the minimum number of days to produce k widgets" — if we can check "is k achievable in d days?" quickly, binary search on d gives O(log(max_days) × check_time). This pattern appears in competitive programming and real optimisation problems constantly.
(lo + hi) / 2 can overflow. In Java with 32-bit int: lo=109, hi=1.5×109: lo+hi = 2.5×109 overflows. Safe form: lo + (hi - lo) / 2. Python integers never overflow, but write the safe form for habit when writing Java/C.Correctness proof by loop invariant
Loop invariant (CLRS §2.1 style): at the start of each iteration, if target is in arr, it is in arr[lo..hi]. Initialisation: lo=0, hi=n-1; the whole array is searched. Maintenance: if arr[mid] < target, target cannot be in arr[0..mid], so setting lo=mid+1 preserves the invariant. Symmetrically for hi=mid-1. Termination: when lo>hi, the search space is empty; if the invariant held, target is not in arr. Therefore -1 is correct.
Interpolation search and exponential search
Interpolation search: instead of mid = (lo+hi)/2, estimate mid = lo + (target-arr[lo])/(arr[hi]-arr[lo]) × (hi-lo). For uniformly distributed data, this gives O(log log n) expected time. For adversarial data, O(n) worst case. Useful when data is approximately uniform and comparisons are expensive. Exponential search: find a range [2k, 2k+1] containing target (O(log n) steps), then binary search within it. Useful for unbounded arrays or when the target is near the beginning.
Cormen, T. H. et al. (2022). CLRS (4th ed.), §2.3.5 — Binary search (exercise). Knuth, D. E. (1998). TAOCP Vol. 3, §6.2.1 — Searching by comparison of keys. Bottenbruch, H. (1962). "Structure and use of ALGOL 60." JACM 9(2) — first correct binary search.