Searching monotone multi-dimensional arrays

A d-dimensional array of real numbers is called monotone increasing if its entries are increasing along each dimension. Given A_n,d, a monotone increasing d-dimensional array with n entries along each dimension, and a real number x, we want to decide whether x∈A_n,d, by performing a sequence of comparisons between x and some entries of A_n,d. We want to minimize the number of comparisons used. In this paper we investigate this search problem, we generalize Linial and Saks’ search algorithm N. Linial, M. Saks, Searching ordered structures, J. Algorithms 6 (1985) 86-103] for monotone three-dimensional arrays to d-dimensions for d?4. For d=4, our new algorithm is optimal up to the lower order terms.