Cache-efficient and hardware-tuned search: branchless binary search, Eytzinger and vEB layouts, learned indexes, SIMD search, and galloping intersection.
| 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 |
Finger SearchSearch starting from a known nearby position, achieving time proportional to distance rather than full size.
Interpolation Sequential SearchEstimate the likely position using interpolation, then refine by local sequential scan.
Learned Index SearchUse a predictive model to estimate where a key should appear, then search within a bounded local range.
Recursive Model Index SearchUse a hierarchy of learned models to predict a key position, then search inside a bounded error range.
Branchless Binary SearchPerform binary search with conditional moves or arithmetic updates instead of unpredictable branches.
Eytzinger Layout SearchBinary search over an array arranged in heap order to improve cache locality and branch predictability.
Van Emde Boas Layout SearchSearch a binary tree stored in recursive cache oblivious layout to reduce memory transfers.
Cache Aware Binary SearchArrange and search sorted data with explicit knowledge of cache lines or memory blocks.
Branchless Lower BoundCompute lower bound using arithmetic or conditional moves instead of branches.
SIMD Linear SearchSearch several array elements at once using vector instructions.
SIMD Binary SearchUse vector instructions to evaluate multiple candidate positions in a binary search step.
Interpolation Search with FallbackUse interpolation to estimate the target position, with binary search fallback when estimates become unreliable.
Galloping Intersection SearchFind intersection of two sorted sequences using exponential jumps followed by binary search.
Merge Path SearchFind diagonal partition points that split a sorted merge into independent balanced ranges.
Exponential Backoff SearchExpand the search range exponentially until the target is bracketed, then refine within the range.