12. Specialized Search and Sorted-Order Procedures
Cache-efficient and hardware-tuned search: branchless binary search, Eytzinger and vEB layouts, learned indexes, SIMD search, and galloping intersection.
12. Specialized search and sorted-order procedures, 15
| index | slug | name |
|---|---|---|
| 336 | exponential-backoff-search | Exponential Backoff Search |
| 337 | finger-search | Finger Search |
| 338 | interpolation-sequential-search | Interpolation Sequential Search |
| 339 | learned-index-search | Learned Index Search |
| 340 | recursive-model-index-search | Recursive Model Index Search |
| 341 | branchless-binary-search | Branchless Binary Search |
| 342 | eytzinger-layout-search | Eytzinger Layout Search |
| 343 | van-emde-boas-layout-search | Van Emde Boas Layout Search |
| 344 | cache-aware-binary-search | Cache Aware Binary Search |
| 345 | branchless-lower-bound | Branchless Lower Bound |
| 346 | simd-linear-search | SIMD Linear Search |
| 347 | simd-binary-search | SIMD Binary Search |
| 348 | interpolation-search-with-fallback | Interpolation Search with Fallback |
| 349 | galloping-intersection-search | Galloping Intersection Search |
| 350 | merge-path-search | Merge Path Search |
Exponential Backoff Search
Expand the search range exponentially until the target is bracketed, then refine within the range.
Finger Search
Search starting from a known nearby position, achieving time proportional to distance rather than full size.
Interpolation Sequential Search
Estimate the likely position using interpolation, then refine by local sequential scan.
Learned Index Search
Use a predictive model to estimate where a key should appear, then search within a bounded local range.
Recursive Model Index Search
Use a hierarchy of learned models to predict a key position, then search inside a bounded error range.
Branchless Binary Search
Perform binary search with conditional moves or arithmetic updates instead of unpredictable branches.
Eytzinger Layout Search
Binary search over an array arranged in heap order to improve cache locality and branch predictability.
Van Emde Boas Layout Search
Search a binary tree stored in recursive cache oblivious layout to reduce memory transfers.
Cache Aware Binary Search
Arrange and search sorted data with explicit knowledge of cache lines or memory blocks.
Branchless Lower Bound
Compute lower bound using arithmetic or conditional moves instead of branches.
SIMD Linear Search
Search several array elements at once using vector instructions.
SIMD Binary Search
Use vector instructions to evaluate multiple candidate positions in a binary search step.
Interpolation Search with Fallback
Use interpolation to estimate the target position, with binary search fallback when estimates become unreliable.