# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms
The special cases when \(j=1\) or \(j=n_{2}\) are such that the values of \(f(i,1),g(i,1),f(i,n_{2})\) and \(g(i,n_{2})\) do not depend on the index \(j\) and are treated separately at the end of this subsection. We first deal with the case when \(1<j<n_{2}\) and construct the functions\(f(i,j)\) and \(g(i,j)\), on the basis of the parity of \(n_{1}\). Case 1 (\(n_{1}\) is odd):

The index \(i\) is uniquely specified as \(i=\lceil n_{1}/2\rceil\) and thus \(i=(n_{1}+1)/2\). Substituting \(i\) in (19), It can be seen that the number of redundant entries reduces to \(f(i,j)=(n_{1}+1)n_{2}/2\), which is independent of \(j\). Thus, it does not matter which entry \(j\) of the \(i^{\text{th}}\) row of \(A\) is identified by the binary search as the pivot (including the cases \(j=1\) and \(j=n_{2}\)). Hence, the number \(g(i,j)\) of entries left to be searched is invariant, where

\[g(i,j)=\frac{(n_{1}-1)n_{2}}{2}. \tag{21}\]

This case is illustrated in Table 1, where \(n_{1}=7,n_{2}=8,i=4,f(4,j)=32\) and \(g(4,j)=24,j=1,\ldots,8\). Case 2 (\(n_{1}\) is even):

The index \(i\) can be specified as either \(i=\lceil n_{1}/2\rceil\) (\(i=n_{1}/2\)) or \(i=\lceil n_{1}/2\rceil+1\) (\(i=n_{1}/2+1\)). For either specification, an obvious task is to identify the column \(j\) of \(A\) that corresponds to the worst case, where the least number of entries is made redundant. This happens when, for a specified row \(i\), binary search returns an index \(j\) corresponding to \(\operatorname{argmin}(f(i,j))\) or, equivalently, to \(\operatorname{argmax}(g(i,j))\). The two specifications of \(i\) are now settled. Case 2(\(a\)) (\(n_{1}\) is even and \(i=n_{1}/2\)):

It can be seen from (19) that \(f(i,j)\) reduces to \((n_{1}+2)n_{2}/2-j\), which is minimal when \(j\) is as large as possible (\(j=n_{2}-1\)). Thus, the number of entries left to be searched is

\[g(i,j)=\frac{n_{1}n_{2}}{2}-1. \tag{22}\]

This case is illustrated in Figure 5b. Case 2(\(b\)) (\(n_{1}\) is even and \(i=n_{1}/2+1\)):

Here \(f(i,j)\) reduces to \((n_{1}n_{2})/2+j\)), which is minimal when \(j\) is as small as possible, i.e., \(j=2\). Thus, the number of entries left to be searched is,

\[g(i,j)=\frac{n_{1}n_{2}}{2}-2. \tag{23}\]

Note that for the separate cases when the binary search returns either \(j=1\) or \(j=n_{2}\) as the pivot, the number of entries left to be searched is \(g(i,n_{2})=(n_{1}n_{2})/2\), which is higher than those in relations (22) and (23). The cases are illustrated in Table 2, where \(n_{1}=6\) and \(n_{2}=8\). As an example of Case 2(\(a\)), if \(i=3\) and \(j=7\), then \(f(3,7)=25\) and \(g(3,7)=23\). However, if \(i=3\) and \(j=1\), then \(f(3,1)=g(3,1)=24\). As an example of Case 2(\(b\)), if \(i=4\) and \(j=2\), then \(f(4,2)=26\) and \(g(4,2)=22\). However, if \(i=3\) and \(j=8\), then \(f(3,8)=g(3,8)=24\). ## 5 Searching the Cuboid (\(d=3\))

### The Balanced Case (the \(n\)-Cube)

For the particular case where \(d=3\), and the array is balanced (an \(n\)-cube), [PERSON] and [PERSON] [5] improved on the bounds in (5) by establishing

\[\left\lfloor\frac{3}{2}n^{2}\right\rfloor\leqslant\tau(n,3)\leqslant\frac{3}{2 }n^{2}+3n\lg(n+2). \tag{24}\]

As the authors mention, the lower bound in the left-most expression of (24) can be established as follows. The worst case instance is given by

\[a(i,j,k)= \begin{cases}-\infty,&\text{if $i+j+k\leqslant 3n/2+1$ and $n$ is even;}\\ -\infty,&\text{if $i+j+k\leqslant 3n/2+3/2$ and $n$ is odd;}\\ +\infty,&\text{otherwise.}\end{cases}  \tag{25}\]

For \(n\) even, if any search algorithm fails to compare \(x\) with any element \(a(i,j,k)\), where:

\[i+j+k=\frac{3}{2}n+1 \tag{26}\]

or

\[i+j+k=\frac{3}{2}n+2, \tag{27}\]

then that element could be equal to \(x\) even though \(A\) is monotone. For \(n\) odd, if any algorithm fails to compare \(x\) with any element \(a(i,j,k)\), where:

\[i+j+k=\frac{3}{2}n+\frac{3}{2} \tag{28}\]

or

\[i+j+k=\frac{3}{2}n+\frac{5}{2}, \tag{29}\]

then that element could be equal to \(x\) even though \(A\) is monotone.