# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms
In the second stage, the L&S algorithm searches for \(x\) in these six subarrays using the adaption of saddleback search for the rectangle. In the worst case, when \(x\) is not found by any of these searches, what is left of the original array \(A\) is a subarray of dimension \((n-2)\times(n-2)\times(n-2)\), to which the algorithm L&S is again applied. The pseudocode of the L&S algorithm is given in Algorithm 10. The specialized version of the binary search in steps 8 to 13 return both an indication of whether the key was found (or not) and its position in the array (or the position of the first entry greater than the key). The operator \(\vee\) in steps 9 to 13 implies that the algorithm is terminated if one of the binary searches along the YBR path finds \(x\). Similarly, in steps 15 to 20, the search is terminated if one of the calls to the specialized version of the saddleback search finds \(x\). It is straightforward to show that the L&S algorithm has the following recurrence for the worst-case number of required comparisons needed to search for a key \(x\):

\[\tau(n,3)\leqslant\tau(n-2,3)+6\lg(n+1)+6(n-1). \tag{30}\]

Figure 6: An example of a remaining subarray after searching part of the YBR path. (**a**) The “Yellow Brick Road”. (**b**) The remaining subarray (the green area). Solving the recurrence (30), establishes the following upper bound on the number of comparisons required by the L&S algorithm [5]. \[\tau(n,3)\leqslant 3n^{2}/2+3n\lg(n+2). \tag{31}\]

```
0: Array \(A((\ell_{1},\ell_{2},\ell_{3}),\ldots,(r_{1},r_{2},r_{3}))\) and key \(x\in\mathbb{R}\). 0: True if \(x\in A\) or False otherwise. 1:if\((\ell_{1}=r_{1})\) and \((a(\ell_{1},\ell_{2},\ell_{3})=x)\)then// Stop conditions. 2:return true
3:endif
4:if\((\ell_{1}=r_{1})\) and \((a(\ell_{1},\ell_{2},\ell_{3})\
eq x)\)then
5:return false. 6:endif
7:\(found\leftarrow\) false; // Stage 1: Search on YBR path. 8:\((i_{1},found)\leftarrow\) BinarySearch\((A((\ell_{1},r_{2},\ell_{3}),\ldots,(r_{1},r_{2},\ell_{3})),x)\);
9:\((k_{1},found)\gets found\)\(\vee\) BinarySearch\((A((\ell_{1},r_{2},\ell_{3}),\ldots,(\ell_{1},r_{2},r_{3})),x)\);
10:\((j_{1},found)\gets found\)\(\vee\) BinarySearch\((A((\ell_{1},\ell_{2},r_{3}),\ldots,(\ell_{1},r_{2},r_{3})),x)\);
11:\((i_{2},found)\gets found\)\(\vee\) BinarySearch\((A((\ell_{1},\ell_{2},r_{3}),\ldots,(r_{1},\ell_{2},r_{3})),x)\);
12:\((k_{2},found)\gets found\)\(\vee\) BinarySearch\((A((r_{1},\ell_{2},\ell_{3}),\ldots,(r_{1},\ell_{2},r_{3})),x)\);
13:\((j_{2},found)\gets found\)\(\vee\) BinarySearch\((A((r_{1},\ell_{2},\ell_{3}),\ldots,(r_{1},r_{2},\ell_{3})),x)\);
14:if not foundthen// Stage 2: Search on A sub-faces. 15:\(found\leftarrow\) SaddlebackSearch\((A((i_{1},j_{2},\ell_{3}),\ldots,(r_{1},r_{2},\ell_{3})),x)\);
16:\(found\gets found\)\(\vee\) SaddlebackSearch\((A((\ell_{1},r_{2},\ell_{1}),\ldots,(i_{1},r_{2},k_{1})),x)\);
17:\(found\gets found\)\(\vee\) SaddlebackSearch\((A((\ell_{1},j_{1},k_{1}),\ldots,(\ell_{1},r_{2},r_{3})),x)\);
18:\(found\gets found\)\(\vee\) SaddlebackSearch\((A((\ell_{1},\ell_{2},r_{3}),\ldots,(i_{2},j_{1},r_{3})),x)\);
19:\(found\gets found\)\(\vee\) SaddlebackSearch\((A((i_{2},\ell_{2},k_{2}),\ldots,(r_{1},\ell_{2},r_{3})),x)\);
20:\(found\gets found\)\(\vee\) SaddlebackSearch\((A((r_{1},\ell_{2},\ell_{3}),\ldots,(r_{3},j_{2},k_{2})),x)\);
21:endif
22:if not foundthen// Recursive call of L&S algorithm. 23:\(found\leftarrow\) L&S\((A((\ell_{1}+1,\ell_{2}+1,\ell_{3}+1),\ldots,(r_{1}-1,r_{2}-1,r_{3}-1)),x)\);
24:endif
25:return found. ```

**Algorithm 10**L&S\((A,x)\)

While the L&S algorithm is worst-case optimal, for small arrays it does not necessarily have the best performance. The approach, denoted here by SBS3, is based on partitioning \(A\) into \(n\) isomorphic copies of its \(\mathbf{2}\)-dimensional subarrays, each consisting of all entries that have identical \(\mathbf{3}^{rd}\) coordinates. Saddleback search is then used repeatedly to search each \(\mathbf{2}\)-dimensional subarray. SBS3 has worst case time complexity of \(\tau(n,3)\leqslant\mathbf{2}n^{2}-n\).