Here&#x27;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: <a href="http:&#x2F;&#x2F;arxiv.org&#x2F;ftp&#x2F;arxiv&#x2F;papers&#x2F;1509&#x2F;1509.05053.pdf" rel="nofollow">http:&#x2F;&#x2F;arxiv.org&#x2F;ftp&#x2F;arxiv&#x2F;papers&#x2F;1509&#x2F;1509.05053.pdf</a>. (Spoiler alert: it&#x27;s not sorted order with binary search, and the answer has a lot to do with the cache).