Table of Contents 1Optimizing Binary Search And Interpolation Search1.1Problem statement 1.2Inspiration and background 1.3Benchmarking setup 2Baseline2.1A note on power-of-two array sizes 3Alternative memory layout3.1Naive implementation 3.2Prefetching 3.3Branchless Eytzinger 3.4Batched Eytzinger3.4.1Non-prefetched 3.4.2Prefetched 4Eytzinger or BinSearch? 5Memory efficiency – parallel search and comparison to B-trees 6Interpolation search 7Comparing everything on the human genome 1 Optimizi...
