# Searching Monotone Arrays: A Survey
## 2 Preliminaries  
Consider a real \(d\)-dimensional array \(A=\{a(i_{1},i_{2},\ldots,i_{d})\mid i_{1}=1,\ldots,n_{1};i_{2}=1,\ldots,n_{2}; \ldots;i_{d}=1,\ldots,n_{d}\}\), that is monotone nondecreasing in the sense that \(a(i_{1},i_{2},\ldots,i_{d})\leqslant a(j_{1},j_{2},\ldots,j_{d})\) if \(i_{1}\leqslant j_{1},i_{2}\leqslant j_{2},\ldots,i_{d}\leqslant j_{d}\), for given, independent, sizes \(n_{1},n_{2},\ldots,\)\(n_{d}\in\mathbb{Z}^{+}\), (i.e., the entries of \(A\) are nondecreasing along its dimensions). \(A\) can be thought of as equivalent to the product of the chains \([n_{1}],[n_{2}],\ldots,[n_{d}]\) of the partially ordered sets \(\{1,\ldots,n_{1}\},\{1,\ldots,n_{2}\},\ldots,\{1,\ldots,n_{d}\}\). A \(d\)-dimensional array \(A\) can be also defined by the indexes of its lower corner and upper corner as \(A((1,1,\ldots,1),\ldots,(n_{1},n_{2},\ldots,n_{d}))\). Similarly, a \(d\)-dimensional subarray of \(A\) is defined as \(A((\ell_{1},\ell_{2},\ldots,\ell_{d}),\ldots,(r_{1},r_{2},\ldots,r_{d}))\), where \(1\leqslant\ell_{i}\leqslant r_{i}\leqslant n_{i}\), for all \(1\leqslant i\leqslant d\). The problem discussed here involves searching \(A\) in order to establish whether or not a given key \(x\in\mathbb{R}\) is a member of \(A\). It is assumed that the search must be carried out by sequentially comparing \(x\) with selected entries \(a(i_{1},i_{2},\ldots,i_{d})\in A\). The purpose of such comparisons is to eliminate elements of \(A\) and search the remaining subarrays in an efficient manner. It is of interest to identify search algorithms that require the minimum number of comparisons in the worst case. When comparing \(x\) and any entry \(a(i_{1},i_{2},\ldots,i_{d})\), one of the three following results must be obtained:  
\[x<a(i_{1},i_{2},\ldots,i_{d}), \tag{1}\]  
in which case the entries \(a(j_{1},j_{2},\ldots,j_{d})\) for \(j_{1}\leqslant i_{1},j_{2}\leqslant i_{2},\ldots,j_{d}\leqslant i_{d}\), can be discarded; or  
\[x=a(i_{1},i_{2},\ldots,i_{d}), \tag{2}\]  
in which case \(x\) has been located and the search is terminated; or  
\[x>a(i_{1},i_{2},\ldots,i_{d}), \tag{3}\]  
in which case the entries \(a(j_{1},j_{2},\ldots,j_{d})\) for \(j_{1}\leqslant i_{1},j_{2}\leqslant i_{2},\ldots,j_{d}\leqslant i_{d}\), can be discarded. It is clear that it is necessary to make two comparisons between \(x\) and any entry \(a(i_{1},i_{2},\ldots,i_{d})\) to cover the three possibilities (1)-(3). Any entry that is discarded by the comparison process as (1) and (3) above (as it cannot possibly be \(x\)) is termed redundant. If, in carrying out the comparison process, an entry \(a(i_{1},i_{2},\ldots,i_{d})\) of \(A\), causes \(A\) to be divided into at least two nondegenerate subarrays, then this entry is termed a pivot. An array \(A\) is said to be \(\alpha\)-balanced if \(n_{i}\leqslant\alpha\cdot n_{i+1}\), \(1\leqslant i\leqslant d-1\), for a given \(\alpha\in\mathbb{R}^{+}\), \(1\leqslant\alpha\leqslant 6.4\). The use of the constant \(6.4\) is justified in the arguments given towards the end of Section 4.2. A 1-balanced array is termed balanced, where \(n_{1}=n_{2}=\cdots=n_{d}=n\) (\(\geqslant 2\)) say, and is a hypercube. If \(n_{i}>6.4\cdot n_{i-1}\), \(2\leqslant i\leqslant d\), \(A\) is termed unbalanced. If the sizes of \(A\) are strictly unequal, \(A\) is a rectangular hypercuboid. From now on, all cuboids and hypercuboids to be searched will be assumed to be rectangular and the term rectangular will be dropped. Suppose \(A\) is a \(d\)-dimensional array with sizes \(n_{1},\ldots,n_{d}\). Let \(\mathcal{M}(A)\) be the the minimum number of comparisons (taken over all possible search algorithms) needed either to establish whether or not a given key \(x\) is in \(A\). We denote \(\mathcal{M}(A)\) by. \[\mathcal{M}(A)= \begin{cases}\tau(n,d),&\text{if $A$ is balanced and $n_{1}=\cdots=n_{d}=n$;}\\ \phi(n_{1},\ldots,n_{d}),&\text{otherwise.}\end{cases}  \tag{4}\]  
When calculating the asymptotic time complexity of an algorithm, in general, the constant term in \(\mathcal{M}(A)\) can be neglected.