This is called the Eytzinger layout [1].
Interesting!
Upvoted!
But, hashes, while tremendously useful for some types of data, are not necessarily without problems for other data, most notably if the data has the possibility of collisions:
https://en.wikipedia.org/wiki/Pigeonhole_principle
https://en.wikipedia.org/wiki/Collision_(computer_science)
https://danlark.org/2020/06/14/128-bit-division/
>"When it comes to hashing, sometimes 64 bit is not enough, for example, because of birthday paradox — the hacker can iterate through random 2^{32} entities and it can be proven that with some constant probability they will find a collision, i.e. two different objects will have the same hash. 2^{32} is around 4 billion objects and with the current power capacity in each computer it is certainly achievable. That’s why we need sometimes to advance the bitness of hashing to at least 128 bits. Unfortunately, it comes with a cost because platforms and CPUs do not support 128 bit operations natively."
So, it depends on the data, and what's being done with it, if the possibility of collisions exist, and what the implications of those possibilities are (perhaps hashes are great for speed, and harmless, if not used with respect to passwords, that is, used in some other place in software infrastructure, they might be the right choice for that place...)
1) Pre-compute the first mid/center element, C1.
2) Move the data for this mid/center element to the first item in a new array.
3) Pre-compute the next two mid/center elements, that is, the ones between the start of the data and C1 (C2), and the one between C1 and the end of data (C3).
4) Move the data from C2 and C3 positions to the next positions in our array, the 2nd and 3rd position.
5) Keep repeating this pattern. For every iteration/split there are 2 times the amount of midpoints/data than the previous iteration. Order these linearly as the next items in our new array.
When you're done, two things will occur.
1) You will use a slightly different binary search algorithm.
That is because you no longer need to compute a mid-point at every iteration, those are now pre-computed in the ordered array.
2) Because the data is now ordered, it becomes possible to load the tip of that data into the CPU's L1, L2, and L3 cache. If let's say your binary search takes 16 iterations to complete, then you might get a good headstart of 5-8 iterations (or more, depending on cache size and data size) of that data being in cache RAM, which will make those iterations MUCH faster.
Also, (and this is just me), but if your program has appropriate permissions to temporarily shut off interrupts (x86 cli sti -- or OS API equivalent), then this search can be that much faster (well, depends on what the overhead for cli/sti and API calls are, but test, test, test! (also, always shut off the network and other threads when you're testing, as they can skewer the results!) <g>)
https://en.wikipedia.org/wiki/Memory_hierarchy
"Almost all programming can be viewed as an exercise in caching." --Terje Mathisen
"Assume Nothing" --Mike Abrash
Also, there is no such thing as the fastest binary search algorithm... there's always a better way to do them...
To paraphrase Bruce Lee:
"There are no mountain tops, there is only an endless series of plateaus, and you must ever seek to go beyond them..."