# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms
This complexity is compared with that of the L&S algorithm \(\tau(n,3)\leqslant(3n/2+3n\lg(n+2))\) in Figure 7. It can be seen that SBS3 is superior when \(n\leqslant 33\) and the L&S algorithm dominates otherwise. ### The Unbalanced Case (the Cuboid)

Of course, the unbalanced 3-dimensional array, the cuboid, is a special case of the hypercuboid. As given in (37) below, [PERSON] and [PERSON] (Theorem 5.3 in [5]) showed that for \(\mathbf{n_{1}}\geqslant\mathbf{n_{2}}\geqslant\cdots\geqslant\mathbf{n_{d}}\); the performance \(\mathbf{\phi(n_{1},\ldots,n_{d})}\) of any search algorithm of the rectangular hypercuboid is bounded above and below by functions of the order of \(\mathbf{\mathcal{O}(n_{1}\cdots n_{d}\lg(\mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[} \mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[}\mathbf{[}



\[\phi(n_{1},n_{2},n_{3})= \begin{cases}1,&\text{if $n_{1}=n_{2}=n_{3}=1$;}\\ \lg(n_{1}+1),&\text{if $n_{1}>1$ and $n_{2}=n_{3}=1$;}\\ \lg(n_{2}+1),&\text{if $n_{2}>1$ and $n_{1}=n_{3}=1$;}\\ \lg(n_{3}+1),&\text{if $n_{3}>1$ and $n_{1}=n_{2}=1$;}\\ \mathcal{O}(\min\{n_{1},n_{2}\}\lg(\frac{\max\{n_{1},n_{2}\}}{\min\{n_{1},n_{ 2}\}}+1)),&\text{if $n_{1},n_{2}>1$ and $n_{3}=1$;}\\ \mathcal{O}(\min\{n_{1},n_{3}\}\lg(\frac{\max\{n_{1},n_{3}\}}{\min\{n_{1},n_{ 3}\}}+1)),&\text{if $n_{1},n_{3}>1$ and $n_{2}=1$;}\\ \mathcal{O}(\min\{n_{2},n_{3}\}\lg(\frac{\max\{n_{1},n_{3}\}}{\min\{n_{1},n_{ 3}\}}+1)),&\text{if $n_{2},n_{3}>1$ and $n_{1}=1$;}\\ \mathcal{O}(\lg(\max\{n_{1},n_{2},n_{3}\}+1)+\\ \phi(n_{1},\lceil n_{2}/2\rceil,\lfloor n_{3}/2\rfloor)+\\ \phi(\lceil n_{1}/2\rceil,\lfloor n_{2}/2\rfloor,n_{3}),&\text{otherwise.} \end{cases}  \tag{32}\]

## 6 Searching in Higher Dimensions (\(d\geqslant 4\))

### Balanced Case (Hypercubes)

[PERSON] et al [9] extended the results of [PERSON] and [PERSON] [5] for the cube, described in Section 5, to \(d\)-dimensional hypercubes for \(d\geqslant 4\). The [PERSON] et al. algorithm is described as a generalization of a particular algorithm (which we call Cheng-4) for the special case \(d=4\). The authors use the lower bound 4/3\(n\)3 - _n/3_\(\leqslant\tau(n,4)\) to the Cheng-4 algorithm, which they showed to be asymptotically tight. Cheng-4 first selects eight particular 2-\(d\) outer faces of the 4-\(d\) hypercube \(A\) and uses an adaptation of the saddleback search to partition each of these eight 2-\(d\) arrays into two surfaces, requiring at most \(8(2n-1)\) tests. These surfaces generate eight 3-\(d\) subarrays of \(A\) that are then searched with at most \(8n^{2}\) tests. Similarly to the L&S algorithm this process reduces the remaining 4-\(d\) hypercube to be searched to one with sizes \((n-2)\). The authors established that, for \(n>2\), the worst case performance of their algorithm is given by

\[\tau(n,4)\leqslant\tau(n-2,4)+8n^{2}+8(2n-1). \tag{33}\]

This recurrence implies that \(\tau(n,4)\leqslant 4/3n^{3}+\mathcal{O}(n^{2})\). Therefore, using their lower bound the authors have shown that

\[4/3n^{3}-n/3\leqslant\tau(n,4)\leqslant 4/3n^{3}+\mathcal{O}(n^{2}), \tag{34}\]

and that the algorithm is asymptotically optimal up to the lower order terms. The partition of each one of the eight 2-\(d\) outer faces of the 4-\(d\) hypercube generates two subsets \(S\) and \(L\), such that \(S\) contains entries smaller than \(x\) and \(L\) contains entries larger than \(x\). These subsets are derived from two 2-dimensional arrays \(u\) and \(v\), each containing \(n\) integers such that \(i_{1}\leqslant u[i_{2}]\) iff \(a(i_{1},i_{2})<x\) and \(i_{2}\leqslant v[i_{1}]\) iff \(a(i_{1},i_{2})<x\). The sets \(S\) and \(L\), as well as the arrays \(u\) and \(v\) are illustrated in Figure 9.

The eight 2-\(d\) outer faces are defined by fixing a pair of subscripts \((i_{p},i_{q})\), \(p=1,\ldots,4\) and \(q=(p+1)\mod 4\), to either \((1,n)\) or \((n,1)\) and are denoted by \(M_{i}\) and \(M_{i}^{*}\), \(i=1,\ldots,4\).