Tag
binary-search
- Nov 17, 2025 Longest Increasing Subsequence and the Tails Array Invariant The O(n log n) patience-sorting method keeps one number per length instead of a full two-dimensional table, and the invariant explaining why is a dominance argument. algorithms
- Jan 6, 2025 Eytzinger Layout: Storing a Search Tree in Level Order How laying out a binary search tree in breadth-first order removes pointer chasing, enables branch-free traversal and prefetching, and what it costs on updates. algorithms
- Jul 1, 2024 Interpolation Search and What Uniform Key Distribution Buys How probing by estimated position turns logarithmic search into log-log search, the exact arithmetic it needs, and the degenerate inputs that make it linear. algorithms
- Jun 6, 2024 Term Dictionary Lookup Structures for Inverted Indexes How an index maps a query term to its postings offset, why the dictionary is kept in memory in a different layout from the postings, and what each structure trades for lookup speed. information retrieval
- Dec 23, 2022 Lower Bound, Upper Bound, and the Invariant That Makes Binary Search Correct Why binary search is best expressed as a loop invariant over a half-open interval, how lower and upper bound answer different questions, and which arithmetic breaks first. algorithms