# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms
### The Location of Pivots when Searching a Row of a 2-d Matrix

The purpose of this subsection is to establish the worst case performance of binary search when it is used as a subroutine to search the middle row of a given 2-dimensional monotone real array \(A\) as part of an algorithm that is designed to search \(A\) for a given key \(x\). [PERSON]'s algorithm [7] and the first algorithm of [PERSON] [8]) utilise such a subroutine. More specifically, suppose that \(A_{n_{1}\times n_{2}}\) with \(n_{1}\leqslant n_{2}\), is such a given array and that binary search is applied to the \(i^{\text{th}}\) row of \(A\), for a given \(i\), \(1\leqslant i\leqslant n_{1}\). That is, the entries, \(a(i,q)\), \(q=1,\ldots,n_{2}\); are to be searched. We assume from now on that the binary search of row \(i\) did not find an instance of the key \(x\), but returned the entry \(a(i,j)\) (\(\
eq x\)), for some column \(j\) of \(A\), \(1\leqslant j\leqslant n_{2}\) (see Algorithm 3). In this case \(a(i,j)\) is used as a pivot by comparing it with \(x\) in order to discard the parts of \(A\) that now become redundant in the sense that \(x\) cannot be a member of them. Let \(f(i,j)\) be the number elements of \(A\) that are thus discarded. The issue to be addressed involves identifying for a given \(i\), which \(j\), where \(1\leqslant j\leqslant n_{2}\), corresponds to the worst case in the sense that using \(a(i,j)\) as the pivot causes the least number of elements of \(A\), to be discarded. That is, \(j\) is worst case if \(j=\operatorname{argmin}f(i,j)\). As will be seen later in the present subsection, it has been established that when:

1. \(n_{1}\) is odd, \(f(i,j)\) is independent of \(j\). 2. \(n_{1}\) is even and \(i=n_{1}/2\), \(f(i,j)\) is minimal when \(j\) is maximal. 3. \(n_{1}\) is even and \(i=n_{1}/2+1\), \(f(i,j)\) is minimal when \(j\) is minimal. The above results are now investigated in some detail. If \(j=1\) (\(j=n_{2}\)), then \(x<a(i,q)\) (\(x>a(i,q)\)) for \(q=1,\ldots,n_{2}\); and the rectangle \(A[(i,1),\ldots,(n_{1},n_{2})]\) (\(A[(1,1),\ldots,(i,n_{2})]\)) is redundant and can be discarded. Otherwise, if \(1<j<n_{2}\), then both \(x>A[i,j]\) and \(x<A[i,j+1]\) hold and the redundant area comprises the two rectangles: \(A_{NE}=A[(i,j+1),\ldots,(n_{1},n_{2})]\) and \(A_{SW}=A[(1,1),\ldots,(i,j)]\). Figure 4(a) may aid the understanding of the following reasoning. Examples are given in Tables 1 and 2 in which a zero (unit) entry represents a number less than (greater than) \(x\). The total number \(f(i,j)\) of redundant entries defined by the ordered pair of indexes \((i,j)\) is:

\[f(i,j)= \begin{cases}(n_{1}-(i-1))n_{2},&\text{if }j=1;\\ n_{2}\,i,&\text{if }j=n_{2};\\ ij+(n_{1}-(i-1))(n_{2}-j),&\text{if }1<j<n_{2}.\end{cases}  \tag{18}\]

A simple algebraic rearrangement of the case \(1<j<n_{2}\) leads to:

\[f(i,j)=(n_{1}+1)n_{2}-n_{2}\,i-(n_{1}+1-2i)j. \tag{19}\]

Clearly, the number of entries left to be searched is \(g(i,j)=n_{1}n_{2}-f(i,j)\), which after some algebraic rearrangement leads to:

\[g(i,j)= \begin{cases}(i-1)n_{2},&\text{if }j=1;\\ (n_{1}-i)n_{2},&\text{if }j=n_{2};\\ n_{2}\,i+(n_{1}+1-2i)j-n_{2},&\text{if }1<j<n_{2}.\end{cases}  \tag{20}\] \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Row \(i\)**} & \multicolumn{8}{c}{**Column \(j\)**} \\ \cline{2-10}  & **1** & **2** & **3** & **4** & **5** & **6** & **7** & **8** \\ \hline
7 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
6 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
5 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Case 1. \(n_{1}\) is odd. Figure 5: The location of pivots when searching a row. (**a**) General row search. (**b**) Row search Case 2(i). Suppose that the middle row of \(A\) is searched (as is done in [PERSON]'s algorithm [7] and in the first algorithm of [PERSON] [8]).