Binary Search — Halve & Conquer

On a sorted range, throw away half each step.

Suno.Sortedarrayhai.Targetnumberdhundho.Linearscanslow—harstepspaceaadhakaro.

Listen. Sorted array. Find the target. Linear scan is slow — halve the search space each step.

0:00 / 0:58

Speed

Practice binary-search Practice search-insert

When to use this

Exact find
Lower/upper bound
Monotonic predicate

C++ template

int L = 0, R = n - 1;
while (L <= R) {
    int mid = L + (R - L) / 2;
    if (a[mid] == target) return mid;
    if (a[mid] < target) L = mid + 1;
    else R = mid - 1;
}
return -1;

Dry run

[1,3,5,7,9,11] target 7 → found at index 3.

Pitfalls

Infinite loop
mid overflow
lower_bound off-by-one

Say this in the interview

O(log n) comparisons.

Problems in this topic (3)

Each opens teach-first (animated when available), then the code panel.