# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms
Then, following the reasoning used to derive Equation (17), it can be established that the worst case performance for the revised [PERSON]'s algorithm is

\[=[(2\lfloor\lg n_{2}\rfloor+1)+(2\lfloor\lg(n_{2}-1)\rfloor+1)] +[(2\lg(\lfloor n_{1}/2\rfloor)+1)\ +\]2

Note that the count in (43) is significantly higher than that in (17). Recall that from (13), the worst case performance of the adaption of saddleback search for the array under study has a worst case performance of \((n_{1}+n_{2}-1)\). However, if it is still assumed that two comparisons are necessary at each iteration of saddleback search, then its worst case performance is

\[=[(2\lfloor\lg n_{2}\rfloor+1)+(2\lfloor\lg(n_{2}-1)\rfloor+1)] +[(2\lg(\lfloor n_{1}/2\rfloor)+1)\ +\]3A comparison of equations (43) and (44) imply that if \(\mathbf{n}_{1}\leqslant\mathbf{n}_{2}<8\mathbf{n}_{1}\), [PERSON]'s algorithm has an inferior worst case performance than that of adapted saddleback search. Conversely, if \(\mathbf{n}_{2}\geqslant\mathbf{8n}_{1}\), the algorithm has a better worst case performance than revised saddleback search. ### The L&S Algorithm Revised

We now establish a revised exact count of the number of comparisons required by the L&S algorithm in the worst case. Suppose that the algorithm is applied to an \(\mathbf{n}\)-cube. Suppose further, that when a binary search subroutine is called as a part of the algorithm it has the worst case performance given in Equation (39). Then, following the reasoning used to derive Equation (31), it can be established that the worst case performance for the revised L&S algorithm is

\[=[(2\lfloor\lg n_{2}\rfloor+1)+(2\lfloor\lg(n_{2}-1)\rfloor+1)] +[(2\lg(\lfloor n_{1}/2\rfloor)+1)\ +\]4

Note that the count in (45) is significantly higher than that in (31). ## 8 Searching for All Occurrences of the Key

We now briefly discuss the extended problem of searching for all occurrences of the key. To be meaningful, \(\mathbf{A}\) must be redefined as a strictly monotone array, i.e., its entries either strictly decrease or strictly increase when moving away from the origin along any path parallel to an axis. When \(\mathbf{d}=\mathbf{1}\), binary search is the basis for efficiently solving some variants of the search problem, such as determining the index of: (\(\mathbf{i}\)) the first occurrence of the key, (\(\mathbf{ii}\)) the last occurrence of the key, or (\(\mathbf{iii}\)) the least element greater than the key, or (\(\mathbf{iv}\)) the greatest element less than the key. Some minor changes to the basic logic of the Binary Search algorithm are enough to solve variants (\(\mathbf{i}\))-(\(\mathbf{iv}\)). A simple combination of the algorithms that solve variants (\(\mathbf{i}\)) and (\(\mathbf{ii}\)) or of those that solve variants (\(\mathbf{iii}\)) and (\(\mathbf{iv}\)) can be used to determine all occurrences of the key. Regarding the case \(\mathbf{d}=\mathbf{2}\), although it was included as an \"existence\" method, [PERSON]'s algorithm [PERSON] (1984) was actually designed to search for all occurrences of the key. For the case \(\mathbf{d}\geqslant\mathbf{3}\), the possibility searching for all occurrences of the key is not discussed in any of the articles cited in the present work. However, certainly, the aforementioned algorithms designed to search for a single instance of the key when \(\mathbf{d}\geqslant\mathbf{3}\) can be extended to search for all occurrences of the key, probably with an increase in complexity. ## 9 Conclusions

The problem of sequentially searching a real \(\mathbf{d}\)-dimensional (\(\mathbf{d}\geqslant\mathbf{1}\)) array for a given key has been extensively investigated. The formal definition of the problem has been revised and algorithms identified in the specialised literature for it and some of its special cases, including those where the array has sizes not necessarily equal, have been described in detail. Many aspects of algorithm performance complexity have also been discussed.