Array Layouts for Comparison based Searching (March 14 2017) 计算机科学

ARRAY LAYOUTS FOR COMPARISON-BASED SEARCHING*Paul-Virak Khuong† and Pat Morin‡March 14, 2017Abstract. We attempt to determine the best order and search algorithm to store n compa- rable data items in an array, A, of length n so that we can, for any query value, x, quickly find the smallest value in A that is greater than or equal to x. In particular, we consider the important case where there are many such queries to the same array, A, which resides entirely in RAM. In addition to the obvious so