Binary Search Visualization for Coding Interviews
Classic, first/last occurrence, rotated array — all three animated.
Concept
Binary search is the first algorithm that makes you feel like an engineer — halving the search space every step turns a 1-billion-element lookup into 30 comparisons. It is the backbone of sorted arrays, B-trees on disk, database range queries, and every 'find the smallest X such that predicate(X) is true' problem. The catch is that the vanilla 'found equal' version is only one of many useful variants: first occurrence of a duplicate key, last occurrence, insertion point, search in a rotated sorted array, and binary search over a monotonic answer space. Getting the loop invariants right is where most implementations go wrong — off-by-one errors in mid, the half-open vs half-closed interval choice, and whether to return -1 or the insertion point all determine correctness.
How it works
The canonical loop keeps two pointers lo and hi bounding a search interval and shrinks it by half each iteration. mid is computed as lo + (hi - lo) / 2 to avoid integer overflow. If a[mid] equals the target, return mid; if less, move lo to mid + 1 because everything at or below mid is too small; otherwise move hi to mid - 1. The loop ends when lo > hi, meaning the key is absent. First-occurrence search changes the equals case: instead of returning, it moves hi to mid - 1 and records mid as a candidate, continuing the search to the left half. Last occurrence does the mirror. Rotated-array search asks: which half is sorted? After picking mid, compare a[lo] to a[mid]. If a[lo] <= a[mid], the left half is sorted — check whether target lies in that range and recurse accordingly; otherwise the right half is sorted. The key insight across all variants is that the loop invariant ('answer lies in [lo, hi]' or 'answer is the first index where predicate is true') must be true before and after every iteration.
Implementation
public final class BinarySearch {
private BinarySearch() {}
public static int binarySearch(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
public static int firstOccurrence(int[] a, int target) {
int lo = 0, hi = a.length - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { ans = mid; hi = mid - 1; }
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
public static int lastOccurrence(int[] a, int target) {
int lo = 0, hi = a.length - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) { ans = mid; lo = mid + 1; }
else if (a[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}
public static int searchRotated(int[] a, int target) {
int lo = 0, hi = a.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (a[mid] == target) return mid;
if (a[lo] <= a[mid]) {
if (target >= a[lo] && target < a[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (target > a[mid] && target <= a[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
}
Complexity
- Time:
O(log n) - Space:
O(1) - Requires:
Sorted (or piecewise sorted) array
Common pitfalls
- Computing mid as (lo + hi) / 2 overflows for large arrays — use lo + (hi - lo) / 2.
- Mixing half-open [lo, hi) with half-closed [lo, hi] conventions in the same codebase.
- First/last occurrence variants that return early on equality instead of continuing the search.
- Rotated search with duplicates — a[lo] == a[mid] is ambiguous and forces a linear scan step.
- Off-by-one when the array has exactly one element — loop must still fire.
Key design decisions & trade-offs
- Linear vs binary search — Chosen: Binary above ~30 elements. Cache-hot linear scan beats branchy binary on tiny arrays; flip is around 16-32 ints.
- Closed vs half-open interval — Chosen: Closed [lo, hi] with <= condition. Easier to reason about for beginners; half-open is idiomatic in C++ STL.
- Binary search vs hash table — Chosen: Binary search when range queries or ordered iteration matter. Hash is O(1) point lookup but loses ordering; B-trees win for disk and range scans.
Practice problems
Interview follow-ups
- Implement binary search on a monotonic predicate — 'min k such that canAllocate(k)'.
- Extend rotated search to handle duplicates gracefully.
- Write binary search over doubles with an epsilon termination condition.
- Use binary search to find the square root of an integer.
Why it matters
Binary Search is a core part of the Searching toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".