Array Layouts for Comparison-Based Searching

Paul-Virak Khuong, Pat Morin

We attempt to determine the best order and search algorithm to store $n$ comparable data items in an array, $A$, of length $n$ so that we can, for any query value, $x$, quickly fin…