SearchingAlgorithmaka bisection, logarithmic search

Binary Search

Find a target in a sorted array by repeatedly halving the search range.

▶ VisualizePattern: Binary SearchPractice (3)
Progress

Overview

Binary search locates a value in a sorted array in O(log n) comparisons. Instead of scanning left to right, it looks at the middle element and discards the half that cannot contain the target.

The same idea generalizes far beyond arrays: any monotonic predicate (false…false true…true) over an ordered search space can be binary searched — for example the smallest speed at which a task finishes in time.

sortedO(log n)divide and conquersearch space

Intuition

A mental model before the formal terms.

Think of guessing a number between 1 and 100 where each guess is answered "higher" or "lower". Guessing 50 first is optimal: whatever the answer, half the candidates vanish. Seven guesses always suffice because 2^7 > 100.

How it works

  1. Maintain a range [lo, hi] that is guaranteed to contain the target if it exists.
  2. Compute mid = lo + (hi - lo) / 2 (avoids overflow in fixed-width integers).
  3. If a[mid] == target, return mid. If a[mid] < target, the target must be to the right: lo = mid + 1. Otherwise hi = mid - 1.
  4. Stop when lo > hi — the range is empty and the target is absent.

Why it works

Sortedness gives the invariant: everything left of mid is ≤ a[mid] and everything right is ≥ a[mid]. So one comparison certifies that an entire half cannot hold the target.

Each iteration at least halves the range, so after ⌈log₂(n+1)⌉ iterations the range is empty.

Recognition

How to tell a problem wants this.

  • The input is sorted, or can be sorted cheaply, and you need O(log n) lookups.
  • The problem asks for the minimum/maximum value satisfying a condition and the condition is monotonic ("smallest capacity such that…").
  • Constraints like n ≤ 10^5 with many queries, or an answer range up to 10^9, hint at searching the answer space.
“sorted array” → Binary Search

Interactive visualization

Play, step, change the input. ← → and space work too.

2
0
↑lo
5
1
8
2
12
3
16
4
23
5
38
6
56
7
72
8
91
9
↑hi
1/7The array is sorted. Search for 23 in [lo, hi] = [0, 9]; the invariant is that the target, if present, lies inside this range.
Being compared with targetTarget foundEliminated
PseudocodeLearn Binary Search →
1lo = 0, hi = n - 1
2while lo <= hi:
3  mid = lo + (hi - lo) // 2
4  if a[mid] == target: return mid
5  if a[mid] < target: lo = mid + 1
6  else: hi = mid - 1
7return -1
Variables
lo0
hi9
target23
Complexity
best O(1)
avg O(log n)
worst O(log n)
space O(1)
Speed

Pseudocode

1lo = 0, hi = n - 1
2while lo <= hi:
3  mid = lo + (hi - lo) // 2
4  if a[mid] == target: return mid
5  if a[mid] < target: lo = mid + 1
6  else: hi = mid - 1
7return -1

Implementations

1from bisect import bisect_left
2from typing import Callable, Sequence
3 
4 
51 · The exact-match form on a sorted sequence
6def binary_search(a: Sequence[int], target: int) -> int:
7    lo, hi = 0, len(a) - 1
8    while lo <= hi:
9        mid = (lo + hi) // 2  # Python ints are unbounded, so no overflow
10        if a[mid] == target:
11            return mid
12        if a[mid] < target:
13            lo = mid + 1
14        else:
15            hi = mid - 1
16    return -1
17 
18 
192 · lower_bound: first index whose value is >= target (the useful form)
20def lower_bound(a: Sequence[int], target: int) -> int:
21    lo, hi = 0, len(a)  # half-open [lo, hi)
22    while lo < hi:
23        mid = (lo + hi) // 2
24        if a[mid] < target:
25            lo = mid + 1
26        else:
27            hi = mid
28    return lo  # in [0, n]; a[lo] >= target, or lo == n if none is
29 
30 
313 · Binary search on the answer: smallest x in [lo, hi] with pred(x) true
32def search_answer(lo: int, hi: int, pred: Callable[[int], bool]) -> int:
33    while lo < hi:
34        mid = (lo + hi) // 2
35        if pred(mid):
36            hi = mid
37        else:
38            lo = mid + 1
39    return lo  # requires pred to be False...False,True...True over [lo, hi]
40 
41 
424 · The standard library already implements lower_bound as bisect_left
43def present(a: Sequence[int], target: int) -> bool:
44    i = bisect_left(a, target)
45    return i < len(a) and a[i] == target
Walkthrough
  1. (lo + hi) // 2 is safe in Python because integers are arbitrary precision — the overflow-avoidance dance in the other three languages is unnecessary here.
  2. lo, hi = 0, len(a) uses the half-open convention that bisect itself uses, so the hand-written lower_bound and bisect_left agree exactly.
  3. search_answer is the monotone-predicate form; bisect cannot express it directly because it searches a sequence, not a predicate.
  4. bisect_left(a, target) *is* lower_bound; present is the standard two-line exact-match wrapper around it.
  5. // is floor division, which for the non-negative indices here is the same as truncation — but not for negative values, where -1 // 2 == -1.
Complexity (this implementation)
time O(log n) · space O(1)

bisect is implemented in C, so it is much faster than the Python-level loop at the same asymptotic cost.

Language notes
  • bisect.bisect_left and bisect.bisect_right are lower_bound and upper_bound; insort_left/insort_right insert while keeping the list sorted (O(n) for the shift).
  • bisect accepts a key= argument since Python 3.10, which removes the old trick of maintaining a parallel list of keys.
  • Arbitrary-precision integers mean (lo + hi) // 2 never overflows — the JDK bug simply cannot happen in Python.
  • sorted() and list.sort() are stable TimSort, and sorted() on mixed types raises TypeError rather than producing a silently wrong order.
Common mistakes in this language
  • Using bisect_right where bisect_left is meant: on duplicates they return opposite ends of the run, which flips the answer to "first occurrence" queries.
  • Calling insort in a loop to build a sorted list, which is O(n²); collect then sort() once instead.
  • Mixing the closed while lo <= hi loop with hi = len(a), which raises IndexError on the first iteration.
Language differences that matter here
  • Overflow: (lo + hi) / 2 overflows a 32-bit int in C++ and truncates past 2^31 under >> in JS/TS; Python integers are unbounded, so only Python can write the naive midpoint safely.
  • Standard library: C++ has binary_search/lower_bound/upper_bound/equal_range, Python has bisect_left/bisect_right/insort, and JavaScript and TypeScript have nothing at all.
  • Default sort order: JavaScript Array.prototype.sort() compares as strings unless given a comparator, so a "sorted" numeric array may not be sorted — a precondition violation the search cannot detect.
  • Comparator convention: C++ and the TypeScript version here take strict-less predicates; Array.prototype.sort takes a signed number; bisect takes an optional key projection instead of a comparator.

Complexity

Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)

Recursive version uses O(log n) stack space.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Sorted data with many lookups.
  • Monotonic answer spaces ("minimum X such that feasible(X)").
  • Finding boundaries: first/last occurrence, insertion point, rotation point.
Avoid it when
  • Unsorted data that is queried once — sorting costs O(n log n), more than a linear scan.
  • Linked lists — no O(1) random access, so halving does not save work.
  • Tiny arrays where a linear scan is faster in practice due to branch prediction.

Alternatives

Linear SearchHash MapJump SearchExponential Search

Common mistakes

  • Off-by-one on hi = mid vs hi = mid - 1 leading to infinite loops.
  • Using (lo + hi) / 2 in fixed-width languages — overflows for large indices.
  • Forgetting that the array must be sorted (or the predicate monotonic).
  • Mixing the two templates (lo <= hi returning -1 vs lo < hi returning a boundary).

Interview patterns

  • Search a rotated sorted array by deciding which half is sorted.
  • Binary search on the answer: Koko eating bananas, split array largest sum, capacity to ship packages.
  • First/last position of an element (lower/upper bound).
  • Search in a 2D sorted matrix by treating it as a flattened array.
Interview questions on this
Mock interviews

Example problems

Find the Duplicate NumbermediumSearch in Rotated Sorted ArraymediumKoko Eating Bananasmedium