Algorithms from zero
Sorting and search: code reading
Crux Read real sorting and search snippets — binary-search off-by-ones, the Lomuto partition, merge stability, and quickselect — predict the bug or behaviour, and pick the fix.
Your altitude — climbing toward senior
ZeroJuniorMiddleSenior
You are at middle altitude — in the skySorting and search bugs hide in the boundaries: a wrong comparison, a half discarded one index too far, a swap that loses stability. Read each snippet the way you would in review and name the defect — or the exact behaviour — before you pick.
Goal
Practise the reviewer’s loop for this unit: trace the invariant in your head, find the off-by-one or the lost guarantee, and choose the minimal correct fix.
Snippet 1 — the infinite loop
function bsearch(arr, target) {
let lo = 0, hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) lo = mid; // discard left
else hi = mid - 1; // discard right
}
return -1;
} Quiz
Completed
On many inputs this hangs forever. What is the bug and the fix?
Heads-up lo <= hi is correct for an inclusive range — it is what lets the final single-element range be checked. The hang comes from lo = mid never advancing, not from the condition.
Heads-up Rounding direction is not the cause. With lo = mid the range fails to shrink regardless of rounding. The fix is lo = mid + 1.
Heads-up Check order does not cause the infinite loop. The defect is the boundary update lo = mid that fails to make progress.
Snippet 2 — the integer-overflow midpoint
int bsearch(int arr[], int n, int target) {
int lo = 0, hi = n - 1;
while (lo <= hi) {
int mid = (lo + hi) / 2; // <-- here
if (arr[mid] == target) return mid;
if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
} Quiz
Completed
This passed every small test but corrupted results on a multi-gigabyte sorted array of 32-bit ints. Why, and what is the canonical fix?
Heads-up They can; the algorithm is fine. The only defect is the lo + hi sum overflowing a 32-bit int. Compute mid = lo + (hi - lo) / 2.
Heads-up lo <= hi is correct and reads only valid indices. The bug is arithmetic overflow in (lo + hi), not the loop boundary.
Heads-up Truncation toward lo is exactly what binary search expects and is harmless here. The real defect is the lo + hi overflow on large indices.
Snippet 3 — the Lomuto partition
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
} Quiz
Completed
What does the returned index guarantee, and why does this scheme make quicksort unstable?
Heads-up It returns wherever the chosen pivot lands after partition, which is its sorted position — not the median unless the pivot happened to be the median. Median-finding is quickselect, a different use of partition.
Heads-up Partition guarantees order relative to the pivot, not balance. An extreme pivot leaves one side empty — the O(n²) worst case. Balance is what good pivot choice buys you.
Heads-up Recursion has nothing to do with stability. Instability comes from swaps moving equal elements across the pivot boundary, losing their original relative order.
Snippet 4 — quickselect for the k-th smallest
function quickselect(arr, k, lo = 0, hi = arr.length - 1) {
const p = partition(arr, lo, hi); // pivot's final index
if (p === k) return arr[p];
if (p < k) return quickselect(arr, k, p + 1, hi);
return quickselect(arr, k, lo, p - 1);
} Quiz
Completed
Quickselect finds the k-th smallest element by reusing partition. What is its complexity, and why is it better than sorting for this task?
Heads-up Sorting does both sides at every level; quickselect recurses into only the side holding k, giving an O(n) average. That is the whole point of selecting instead of sorting.
Heads-up Each partition still scans O(n) elements, so a single level is linear. The geometric sum of one-sided recursion is O(n) average, not O(log n).
Heads-up Quickselect deliberately works on unsorted input — partition needs no sortedness. Its worst case is O(n²) on bad pivots, fixed by randomization or median-of-medians.
Recap
Every defect here lives at a boundary: binary search must shrink the range (lo = mid + 1, never lo = mid) and compute mid = lo + (hi - lo) / 2 to dodge overflow; Lomuto partition returns the pivot’s final sorted position and is unstable because swaps cross equal keys; and quickselect reuses that partition to find the k-th element in O(n) average by recursing into only one side. Read the invariant first, then the fix is usually one token.