# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms
For example, \(M_{1}\) is obtained by the indexes \(a(i_{1},i_{2},1,n)\), \(i_{1},i_{2}=1,\ldots,n\), and generates the partitions \(S_{1}\) and \(L_{1}\). Similarly, \(M_{1}^{*}=\{a(i_{1},i_{2},n,1)\}\), \(i_{1},i_{2}=1,\ldots,n\), generates \(S_{1}^{*}\) and \(L_{1}^{*}\). Using some properties as to whether or not the key belongs to the 2-\(d\) partitions, eight 3-\(d\) surfaces \(Q_{i}=\{a(i_{1},i_{2},i_{3},i_{4})\}\) and \(Q_{i}^{*}=\{a(j_{1},j_{2},j_{3},j_{4})\}\) are defined, by fixing \(i_{k}=1\) and \(j_{k}=n\) for \(k=1,\ldots,4\). The search then proceeds in some subarrays of these eight surfaces generated by the intersections induced by the partitions \(S_{i}\) and \(L_{i}\) (\(S_{i}^{*}\) and \(L_{i}^{*}\)). An example of these intersections is depicted in Figure 10. For further details the reader is referred to [9]. [PERSON] et al. [9] also showed how the algorithm Cheng-4 can be generalised to \(d\)-dimensional hypercubes, for \(d\geq 5\), in a straightforward way. As with Cheng-4, the search is carried out in two steps. In the first step, the algorithm partitions the original matrix \(A_{n,d}\) into \(2d\) subsets \(S_{k}\) and \(L_{k}\), \(k=1,\ldots,d\); such that \(S_{k}\) contains entries smaller than \(x\) and \(L_{k}\) contains entries larger than \(x\). The algorithm considers \(2d\)\((d-2)\)-dimensional arrays as defined below:

\[M_{k}=\{a(i_{1},i_{2},\ldots,i_{d})\mid i_{k-2}=1,i_{k-1}=n\} \Rightarrow S_{k},L_{k},\] \[M_{k}^{*}=\{a(i_{1},i_{2},\ldots,i_{d})\mid i_{k-2}=n,i_{k-1}=1\} \Rightarrow S_{k}^{*},L_{k}^{*}.\]

The aim of using the subsets \(S_{k}\) and \(L_{k}\) is to attempt to eliminate part of the surface of a particular subarray by fixing \((d-3)\) subscripts. The \(d\) pairs of \"mutually complementary\" subsets \((S_{k},L_{k})\) and \((S_{k}^{*},L_{k}^{*})\)\((k=1,\ldots,d)\) have the following properties:

1. \(x>a(i_{1},\ldots,i_{d}\mid i_{(k-2)\mod d}=1,i_{(k-1)\mod d}=n)\) and \(x<a(j_{1},\ldots,j_{d})\mid j_{(k-2)\mod d}=1,j_{(k-1)\mod d}=n)\) for \((i_{k},\ldots,i_{k+d-3})\in S_{k}\) and \((j_{k},\ldots,j_{k+d-3})\in L_{k}\),
2. \(x>a(i_{1},\ldots,i_{d}\mid i_{(k-2)\mod d}=n,i_{(k-1)\mod d}=1)\) and \(x<a(j_{1},\ldots,j_{d})\mid j_{(k-2)\mod d}=n,j_{(k-1)\mod d}=1\) for \((i_{k},\ldots,i_{k+d-3})\in S_{k}^{*}\) and \((j_{k},\ldots,j_{k+d-3})\in L_{k}^{*}\),

for all \(k=1,\ldots,d\). Figure 9: Partition of a monotone two-dimensional array \(A_{n,2}\) corresponding to an outer 2-\(d\) face of A 4-\(d\) hypercube. Adapted from [PERSON] et al. (a) Vector \(u\) and partitions \(S\) and \(L\). (**b**) Vector \(v\) and partitions \(S\) and \(L\). [9]. In total, the first step produces \(\mathbf{4}d\)\(\mathbf{(d-3)}\)-dimensional arrays. At most \(\mathbf{2}n-\mathbf{1}\) comparisons are needed for each fixed subscript \(i_{2},\ldots,i_{d-3}\) and hence at most \(2\mathbf{d}n^{d-4}(\mathbf{2}n-\mathbf{1})\) comparisons in total are required. In the second step, the surfaces of the subarrays are searched in order to reduce the region of uncertainty to a \(\mathbf{d}\)-dimensional array with sizes at most \((\mathbf{n-2})\). The algorithm searches the following \(\mathbf{2}d\)\(\mathbf{(d-1)}\)-dimensional surfaces of \(\mathbf{A}_{n,d}\), that are defined by fixing one of the subscripts at either \(\mathbf{1}\) or \(\mathbf{n}\):

\[Q_{k}=\{\mathbf{a}(i_{1},\ldots,i_{d})\mid i_{k}=\mathbf{1}\},\]\[Q_{k}^{*} =\{a(i_{1},\ldots,i_{d})\mid i_{k}=n\},\] \[k =1,\ldots,d.\]

In total, the second step requires at most \(2 dn^{d-2}\) comparisons. Steps 1 and 2 reduce the original array to a \(d\)-dimensional array \(A_{n-2,d}\), with sizes of at most \((n-2)\). That is,

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

Hence the generalised recursion is:

\[\tau(n,d)\leqslant \begin{cases}1,&\text{if $n=1$;}\\ 2d,&\text{if $n=2$;}\\ \tau(n-2,d)+2 dn^{d-2}+2 dn^{d-4}(2n-1),&\text{for $n>2$.}\end{cases}