4 ms·

Here's a related paper (on HN last month) which tries to find the arrangement of elements in an array which minimizes search time, measuring wall-clock time rat

by evanpw 11y ago

Here's a related paper (on HN last month) which tries to find the arrangement of elements in an array which minimizes search time, measuring wall-clock time rather than theoretical complexity: http://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf http://arxiv.org/ftp/arxiv/papers/1509/1509.05053.pdf. (Spoiler alert: it's not sorted order with binary search, and the answer has a lot to do with the cache).

mtdewcmu 11y ago
Interesting. One layout they did not consider is the bit-reversal permutation[1] of the sorted array. Searching is straightforward: to find element i, you reverse the bits of i -- so then, you can just binary search. This layout is similar to Eytzinger, so it should perform at least as well, and it may have some advantages. [1]https://en.wikipedia.org/wiki/Bit-reversal_permutation https://en.wikipedia.org/wiki/Bit-reversal_permutation