Binary Search

Mindmap

Binary Search

What are we searching?

An index

value lives in the array

A boundary

bisect left / right

An answer value

search on the answer

Pitfalls

lo < hi vs lo <= hi

hi = len vs len - 1

duplicates

glide left or right

Precondition

Sorted input

or sortable in O(N log N)

Monotone predicate

false…false true…true

The Invariant

lower-bound template

Range [lo, hi]

answer always inside

Loop while lo < hi

stop at one survivor

mid = lo + (hi - lo) // 2

left-biased, overflow-safe

Move

too small

lo = mid + 1

candidate

hi = mid

+

−

⟲

⛶

Problem Categories

Binary Search

O(log N), O(sort)

Classic

Bisect toolkit

left / right

reversed

Boundaries

first & last

Slight variants

derived predicate

Math - square

Missing elements

Rotated

find pivot, split

Peaks

walk uphill

H-Index

Monotone Function

Split input array

Kth smallest

Secondary Loop

Bisect derivatives

2D matrix

Intersection

Custom bisect

+

−

⟲

⛶

Anatomy: One Template to Rule Them All

Almost every problem here is the same lower-bound loop with the comparison swapped out. Master this shape and the variants become trivial.

lo, hi = 0, len(arr) - 1

while lo < hi:

mid = lo + (hi - lo) // 2

if predicate(mid): # mid is too small / not yet the answer

lo = mid + 1

else: # mid could be the answer - keep it

hi = mid

return lo # lo == hi: the leftmost index where predicate is False

The only things that change between problems:

Knob	Options	Why it changes
What predicate(mid) tests	arr[mid] < target, cited(mid) > arr[mid], canNotShip(mid), ...	The "thing" being searched - a value, a boundary, or a feasibility answer
hi start	len(arr) - 1 vs len(arr)	Whether the answer can sit one past the last index (insert positions, missing counts)
lo < hi vs lo <= hi	survivor check vs in-loop return	Lower-bound style returns one survivor; the <= style returns on a direct hit
Glide direction	< for leftmost, <= for rightmost	How duplicates of target are handled

Three things we ever search

• An index - the value lives directly in a sorted array (704, 35, peaks, rotated).
• A boundary - we want where a value would go, then read the [left, right) span (the bisect_* toolkit, 34).
• An answer value - the array isn't searched at all; we bisect a numeric range and verify each candidate with a monotone predicate (875, 1011, sqrt).

When the input isn't sorted

If the predicate is monotone but the array isn't, an O(N log N) sort up front still lands us in O(N log N) overall - which is why "sort, then bisect" appears throughout this section.