Searching: Linear, Binary and Variants
Linear search counts; iterative binary search with its loop invariant and exact worst-case probe count, average successful and unsuccessful probes; first and last occurrence, lower and upper bound and counting duplicates, with traces; search and minimum in a rotated sorted array and why duplicates break it; interpolation search and its uniform-key assumption; ternary and exponential search; the comparison lower bound for searching a sorted array. All traces come from a script with 0-based indices.