#cache-aware

Cache Aware Binary Search

Cache Aware Binary Search Cache aware binary search modifies ordinary binary search to account for the memory hierarchy. The algorithm still uses ordering and comparisons, but the data layout or search strategy is chosen with explicit knowledge of cache line size, block size, or page size. The goal is to reduce cache misses. On modern hardware, a comparison is cheap, while an unpredictable memory load can be expensive. Problem Given...