# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms
Similarly, in the diagonal-searching procedure the worst case occurs when \(i=\lceil n_{1}/2\rceil\). Therefore, given (14) and (15), both algorithms approaches have worst case time complexity of \(\phi(n_{1},n_{2})=\mathcal{O}(n_{1}\lg(2n_{2}/n_{1}))=\mathcal{O}(n_{1}\lg(n_ {2}/n_{1}))\), which is asymptotically optimal. #### 4.2.2 [PERSON]'s Algorithm

[PERSON]'s Algorithm [7] uses a row-searching approach that is similar to that of [PERSON]. A binary search is conducted on the middle row of \(A\) to find a pivot \(a(i,j)\) such that \(a(i,j)\leqslant x<a(i,j+1)\). If \(x>a(i,j)\) then the search continues only on the two matrices \(A_{NE}\) and \(A_{SE}\) of reduced size. The algorithm does not perform the two first comparisons of Shen's Algorithm (Lines 6 and 8), proceeding directly to search in the two submatrices of reduced size (Lines 13 and 14). [PERSON] provided the following recurrence to express the asymptotic worst case of his algorithm:

\[\phi(n_{1},n_{2})= \begin{cases}\mathcal{O}(\lg n_{1}),&\text{if $n_{2}=1$;}\\ \mathcal{O}(\lg n_{2}),&\text{if $n_{1}=1$;}\\ 2\phi(\lceil n_{1}/2\rceil,\lceil n_{2}/2\rceil)+\mathcal{O}(\lg(n_{2})),& \text{otherwise;}\end{cases}  \tag{16}\]

and hence has time complexity \(\mathcal{O}(n_{1}\lg(\lceil n_{2}/n_{1}\rceil))\), which is asymptotically optimal. We now establish an exact count of the number of comparisons required by [PERSON]'s algorithm in the worst case. Suppose that the algorithm is applied to a 2-dimensional \(n_{1}\times n_{2}\) array with \(n_{1}\leqslant n_{2}\). Since \(n_{1}\) (\(n_{2}\)) is an integer in a closed range delimited by two consecutive powers of two, the complexity analysis can be done considering that the worst case occurs when \(n_{1}\) (\(n_{2}\)) is the upper bound of the range, as assumed in the following development:

\[\phi(n_{1},n_{2}) \leqslant\lg n_{2}+2\phi(n_{1}/2,n_{2}/2)\] \[=\lg n_{2}+2\lg(n_{2}/2)+2^{2}\phi(n_{1}/2^{2},n_{2}/2^{2})\] \[\vdots\] \[=\lg n_{2}+2\lg(n_{2}/2)+2^{2}\lg(n_{2}/2^{2})+\cdots+2^{i-1} \lg(n_{2}/2^{i-1})+\] \[\qquad 2^{i}\phi(n_{1}/2^{i},n_{2}/2^{i})\] \[=\lg n_{2}+2(\lg n_{2}-\lg 2)+2^{2}(\lg n_{2}-\lg 2^{2})+ \cdots+2^{i-1}(\lg n_{2}-\lg 2^{i-1})+\] \[\qquad 2^{i}\phi(n_{1}/2^{i},n_{2}/2^{i})\] \[=\lg n_{2}\sum_{k=0}^{i-1}2^{k}-\sum_{k=0}^{i-1}k2^{k}\,+2^{i} \phi(n_{1}/2^{i},n_{2}/2^{i}).\]

When \(n_{1}/2^{i}=1\), \(n_{2}/2^{i}>1\). Thus \(i=\lg n_{1}\) and \(\phi(n_{1}/2^{i},n_{2}/2^{i})=\phi(1,n_{2}/2^{\lg n_{1}})=\phi(1,n_{2}/n_{1})= \lg(n_{2}/n_{1})\). Then:

\[\phi(n_{1},n_{2})\leqslant\lg n_{2}\sum_{k=0}^{i-1}2^{k}-\sum_{k=0}^{i-1}k2^{k }+2^{i}\phi(n_{1}/2^{i},n_{2}/2^{i})\]

Figure 4: The two searching schemes in the algorithm of Shen. (**a**) The row searching scheme. (**b**) The diagonal searching scheme. \[=\lg n_{2}+2\lg(n_{2}/2)+2^{2}\phi(n_{1}/2^{2},n_{2}/2^{2})\]0 \[=\lg n_{2}+2\lg(n_{2}/2)+2^{2}\phi(n_{1}/2^{2},n_{2}/2^{2})\]1 \[=\lg n_{2}+2\lg(n_{2}/2)+2^{2}\phi(n_{1}/2^{2},n_{2}/2^{2})\]2 \[=\lg n_{2}+2\lg(n_{2}/2)+2^{2}\phi(n_{1}/2^{2},n_{2}/2^{2})\]3 \[=\lg n_{2}+2\lg(n_{2}/2)+2^{2}\phi(n_{1}/2^{2},n_{2}/2^{2})\]4 \[=\lg n_{2}+2\lg(n_{2}/2)+2^{2}\phi(n_{1}/2^{2},n_{2}/2^{2})\]5

Thus, [PERSON]'s algorithm has worst case performance

\[=\lg n_{2}+2\lg(n_{2}/2)+2^{2}\phi(n_{1}/2^{2},n_{2}/2^{2})\]6

A comparison of (13) and (17) leads easily to the following deductions (which also establish the parameter 6.4 as the basis for defining the phrase unbalanced array). If \(n_{1}\leqslant n_{2}\leqslant 6.4\cdot n_{1}\), [PERSON]'s algorithm has an inferior worst case performance than that of saddleback search. Conversely, if \(6.4\cdot n_{1}<n_{2}\), and thus the array is unbalanced, the algorithm has a better worst case performance than saddleback search.