# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms
 \tag{35}\]

Solving this recursion leads to a worst case performance of the algorithm of

\[\tau(n,d)\leqslant\left(\frac{d}{d-1}\right)n^{d-1}+\mathcal{O}(n^{d-2}),\,d \geqslant 4. \tag{36}\]

### Unbalanced Case (the Hypercuboids)

For the general case of a \(d\)-dimensional array that is not necessarily balanced, [PERSON] and [PERSON] (2006) proved that, for \(n_{1}\geqslant n_{2}\geqslant\cdots\geqslant n_{d}\); there exists a nonincreasing function \(k_{1}(d)\) and a function \(k_{2}(d)\) such that the performance \(\phi(n_{1},\ldots,n_{d})\) of any search algorithm is bounded as follows:

\[k_{2}(d)n_{1}\cdots n_{d-1}\lg(\frac{n_{d}}{n_{d-1}}+1)\leqslant\phi(n_{1}, \ldots,n_{d})\leqslant k_{1}(d)n_{1}\cdots n_{d-2}\lg(\frac{n_{d}}{n_{d-1}}+1), \tag{37}\]

## 7 The Worst Case Performance of Some of the Revised Algorithms

From (8), the binary search of a sorted one-dimensional array of size \(n\) can be performed with \(\lfloor\log(n)\rfloor+1\) comparisons in the worst case. However, there is some justification in assuming that using (1), (2) and (3) at each iteration of such a binary search actually requires two comparisons (not one). Some implications of making such an assumption are now established. ### Binary and \(k\)-Nary Search Revised

The worst case performance of the binary search version that uses only one comparison at each iteration, as described in Section 3, can be stated as follows:

\[\tau(n,1)\leqslant \begin{cases}1,&\text{if $n=1$;}\\ 1+\tau(\lfloor n/2\rfloor,1),&\text{otherwise.}\end{cases}  \tag{38}\]

Therefore,

\[\tau(n,1) \leqslant 1+\tau(\lfloor n/2\rfloor,1)\] \[=1+1+\tau(\lfloor n/2\rfloor/2,1)\] \[\vdots\] \[=\underbrace{1+\cdots+1}_{i}+\tau(\lfloor n/2\rfloor/2^{i-1},1)\] \[=\underbrace{1+\cdots+1}_{i}+\tau(\lfloor n/2^{i}\rfloor,1)\] \[=i+\tau(\lfloor n/2^{i}\rfloor,1).\]When \(\lfloor n/2^{i}\rfloor=1\), \(\tau(\lfloor n/2^{i}\rfloor,1)=\tau(1,1)=1\). Moreover,

\[\lfloor n/2^{i}\rfloor=1 \Rightarrow 1\leqslant n/2^{i}<2\] \[\Rightarrow 2^{i}\leqslant n<2^{i+1}\] \[\Rightarrow 1\lg 2^{i}\leqslant\lg n<\lg 2^{i+1}\] \[\Rightarrow i\leqslant\lg n<i+1\] \[=1+1+\tau(\lfloor n/2\rfloor/2,1)\]0

Thus,

\[=1+1+\tau(\lfloor n/2\rfloor/2,1)\]1

This result can be generalised to \(k\)-ary versions of the algorithm, i.e., that divide the search space into \(k\) parts, as follows:

\[\tau(n,1)\leqslant \begin{cases}c_{k},&\text{if $n<k$;}\\ b_{k}+\tau(\lfloor n/k\rfloor,1),&\text{otherwise;}\end{cases}  \tag{40}\]

where \(c_{k}\) is a tight upper bound on the number of comparisons necessary to check the elements still eventually remaining after exiting the search loop and \(b_{k}\) expresses the complexity of dividing the search space into \(k\) parts, defined by \(k-1\) pivot elements, and the necessary comparisons of the key \(x\) with those pivot elements. Thus,

\[\tau(n,1)\leqslant b_{k}\lfloor\log_{k}n\rfloor+c_{k}. \tag{41}\]

Thus, as \(k\) increases, the logarithm basis and the constants \(c_{k}\) and \(b_{k}\) also increase since more operations are necessary to determine in which subspace to continue the search. Therefore, in practice, the gain of performance obtained by increasing the logarithm basis is practically cancelled out by increasing the constants \(c_{k}\) and \(b_{k}\). ### [PERSON]'s Algorithm Revised

We now establish a revised exact count of the number of comparisons required by the [PERSON]'s row search algorithm [8] in the worst case. The worst possible location of the pivot on the \"middle\" row of the matrix, discussed in Section 4.3, leads to the following revised recurrence relation for the algorithm:

\[\phi(n_{1},n_{2})\leqslant \begin{cases}1,&\text{if $n_{2}=n_{1}=1$;}\\ 2\lfloor\lg n_{2}\rfloor+1,&\text{if $n_{2}>1$ and $n_{1}=1$;}\\ 2\lfloor\lg n_{1}\rfloor+1,&\text{if $n_{2}=1$ and $n_{1}>1$;}\\ (2\lfloor\lg n_{2}\rfloor+1)\ +&\\ (2\lfloor\lg(\lceil n_{1}/2\rceil-1)\rfloor+1)\ +&\\ \phi(\lfloor n_{1}/2\rfloor,n_{2}-1),&\text{otherwise.}\end{cases}