# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms  
Shen [8] proposed both diagonal-searching and row-searching matrix partitioning algorithms, which are asymptotically worst case optimal for unbalanced arrays. A slightly different algorithm from the latter, which uses linear search instead of binary search in the row-searching step, but achieving the same asymptotic complexity, was proposed previously by [PERSON] et al. [32] in a context of geometric applications. The pseudocode of [PERSON]'s row-searching procedure is given in Algorithm 9. The algorithm starts by comparing the key \(x\) with the two extremes of the middle row of an array \(A((1,1),\ldots,(n_{1},n_{2}))\), initially being \(\ell_{1}=1\), \(\ell_{2}=1\), \(r_{1}=n_{1}\) and \(r_{2}=n_{2}\), which has row index \(i\), say. If \(x<a(i,1)\), the submatrix \(A((i,1),\ldots,(n_{1},n_{2}))\) is discarded. If \(x>a(i,n_{2})\), the submatrix \(A((1,1),\ldots,(i,n_{2}))\) is discarded. Otherwise, a binary search on row \(i\) generates a pivot \(a(i,j)\) that allows the submatrices \(A_{SW}=A((1,1),\ldots,(i,j))\) and \(A_{NE}=A(i,j+1),\ldots,(n_{1},n_{2}))\) to be discarded. The algorithm proceeds by searching recursively on submatrices \(A_{NW}=A((i+1,1),\ldots,(n_{1},j))\) and \(A_{SE}=A((1,j+1),\ldots,(i-1,n_{2}))\). The submatrices \(A_{NW}\), \(A_{NE}\), \(A_{SW}\) and \(A_{SE}\) are depicted in Figure 3(a). Algorithm 9 has time complexity given by the following recurrences:  
\[\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;\\ \phi(\lfloor n_{1}/2\rfloor,j)+\phi(\lfloor n_{1}/2\rfloor,n_{2}-j)+\mathcal{O }(\lg(n_{2})),&\text{otherwise}.\end{cases}  \tag{14}\]  
In the diagonal-searching procedure, [PERSON]'s algorithm [8] divides the \(n_{1}\times n_{2}\) matrix \(A\) into \(\lceil\frac{n_{2}}{n_{1}}\rceil\) submatrices of dimensions at most \(n_{1}\times n_{1}\) and uses binary search to find a pivot element \(a(i,j)\) on the main diagonal of the \"middle\" submatrix such that \(a(i,j)<x<a(i+1,j+1)\). This pivot splits the matrix into four possible non empty submatrices \(A_{NW}\), \(A_{NE}\), \(A_{SW}\) and \(A_{SE}\), as depicted in Figure 3(b). Similarly to the row searching schema, the pivot \(a(i,j)\) allows both submatrices \(A_{NE}\) and \(A_{SW}\) to be discarded. Therefore, the search only needs to continue on the two matrices \(A_{NW}=A((i+1,1),\ldots,(n_{1},j))\) and \(A_{SE}=A((1,j+1),\ldots,(i,n_{2}))\) of reduced size. [PERSON]'s diagonal-searching procedure has time complexity given by the following recurrences:  
\[\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;\\ \mathcal{O}(n_{1}),&\text{if }n_{1}=n_{2}\\ \phi(n_{1}-i,j)+\phi(i,n_{2}-j)+\mathcal{O}(\lg(n_{2})),&\text{otherwise}.\end{cases}  \tag{15}\]```
0: Array \(A((\ell_{1},\ell_{2}),\ldots,(r_{1},r_{2}))\) and key \(x\in\mathbb{R}\). 0: True if \(x\in A\) or False otherwise. 1:\(found\leftarrow\)false; // Stop conditions. 2:if\((r_{1}-\ell_{1}+1<4)\)or\((r_{2}-\ell_{2}+1<4)\)then
3: Use BinarySearch in rows/columns; exit;
4:endif
5:\(i\leftarrow\lfloor\frac{\ell_{1}+r_{1}}{2}\rfloor\);
6:if\((x<a(i,\ell_{2}))\)then
7:\(found\leftarrow\)SHEN(\(A((\ell_{1},\ell_{2}),\ldots,(i-1,r_{2})),x\)); // Recursion on submatrix SW-SE. 8:elseif\((x>a(i,r_{2}))\)then
9:\(found\leftarrow\)SHEN(\(A((i+1,\ell_{2}),\ldots,(r_{1},r_{2})),x\)); // Recursion on submatrix NW-NE. 10:else
11:\(j\leftarrow\)BinarySearch(\(A((i,\ell_{2}),\ldots,(i,r_{2})),x\)); // \(a(i,j)\leqslant x<a(i,j+1)\)? 12:if\((x\
eq a(i,j))\)then
13:\(found\leftarrow\)SHEN(\(A((i+1,\ell_{2}),\ldots,(r_{1},j)),x\)); // Recursion on NW. 14:\(found\leftarrow\)SHEN(\(A((\ell_{1},j+1),\ldots,(i-1,r_{2})),x\)); // Recursion on SE. 15:else
16:\(found\leftarrow\)True;
17:endif
18:endif
19:return\(found\). ```

**Algorithm 9** SHEN\((A,x)\)

Then showed that Algorithm 9 has worst case performance when submatrices \(A_{NW}\) and \(A_{SE}\) have the same size, that is, \(j=\lfloor n_{2}/2\rfloor\).