# Searching Monotone Arrays: A Survey
## 4 The Search of Matrices (\(d=2\))
### Unbalanced Matrices
#### 4.2.1 [PERSON]'s Algorithms
It is straightforward to compute the number of elements satisfying (26) and (27). As an illustration, for (26) we must enumerate the number of triples \((i,j,k)\) in the range \(1,\ldots,n\) that sum to \(3n/2+1\). To do this, one should count the number of triples for which \(i,j,k\geqslant 1\) and subtract from it the number of triples for which at least one of \(i,j,k>n\). The number of triples that sum to \(3n/2+1\) is \(\binom{3n/2}{2}\). The number of triples that sum to \(3n/2+1\) with a term bigger than \(n\) is \(\binom{3n/2}{2}\). Thus, the total is \(\binom{3n/2}{2}-3\binom{n/2}{2}\), which is \(3n^{2}/4\). For the expression in (27) it is necessary to count the number of triples \((i,j,k)\), in the range \(1,\ldots,n\); that sum to \(3n/2+2\), which is \(\binom{3n/2+1}{2}\). The number of triples that sum to \(3n/2+2\) with a term bigger than \(n\) is \(\binom{3n/2+1}{2}\). Hence the total is \(\binom{3n/2+1}{2}-3\binom{n/2+1}{2}\), which is also \(3n^{2}/4\). Therefore the number of elements satisfying (26) and (27) is \(3n^{2}/2\). The number of elements satisfying (28) and (29) follows analogously, which is \(\lfloor 3n^{2}/2\rfloor\). Thus the first inequality in (24) is proven. [PERSON] and [PERSON] [5] established the upper bound in the right-most expression of (24) by constructing an algorithm (termed the L&S Algorithm here) with worst case performance equal to the bound. As the constant of the right-most expression in (24) is positive, the L&S algorithm is asymptotically tight in the worst case. An outline of the algorithm follows. It alternates between applying binary search along a closed path of particular vectors and by applying Saddleback Search described in Section 4.1 for a rectangle, which progressively reduces \(n\) by two units at each iteration. At the first stage of the first iteration of the algorithm, binary searches for \(x\) are conducted along six vectors that together form what we call the Yellow Brick Road (The Yellow Brick Road is a fictional element in the children'snovel The Wonderful Wizard of Oz by United States author [PERSON] (1900)) (YBR) cycle. The simplified diagram in Figure 5(a) illustrates this cycle, which comprises paths that connect the following entries of \(A\): \(r=a(n,n,1)\), \(s=a(n,1,1)\), \(t=a(n,1,n)\), \(u=a(1,1,n)\), \(v=a(1,n,n)\) and \(w=a(1,n,1)\). The paths of the initial YBR cycle are the vectors that connect the ordered pairs of entries: \((r,s)\), \((s,t)\), \((t,u)\), \((u,v)\), \((v,w)\) and \((w,r)\). These paths can be represented as the vectors: \(\langle a(n,j_{1},1),j_{1}=1,\ldots,n\rangle\), \(\langle a(n,1,k_{1}),k_{1}=1,\ldots,n\rangle\), \(\langle a(i_{1},1,n),i_{1}=1,\ldots,n\rangle\), \(\langle a(1,j_{2},n),j_{2}=1,\ldots,n\rangle\), \(\langle a(1,n,k_{2}),k_{2}=1,\ldots,n\rangle\) and \(\langle a(i_{2},n,1),i_{2}=1,\ldots,n\rangle\), respectively. The binary searches along these paths identify indexes \(j_{1}\), \(k_{1}\), \(i_{1}\), \(j_{2}\), \(k_{2}\) and \(i_{2}\), respectively, such that \(x>v^{\prime}\), \(\forall\ v^{\prime}\in\{a(i_{1},n,1),a(i_{2},1,n),a(1,j_{1},n),a(n,j_{2},1),a(1, k_{1}),\)\(a(n,1,k_{2})\}\) and \(x<v^{\prime\prime}\), \(\forall\ v^{\prime\prime}\in\{a(i_{1}+1,n,1),a(i_{2}+1,1,n),a(1,j_{1}+1,n),a(n, j_{2}+1,1),a(1,n,k_{1}+1),a(n,1,k_{2}+1)\}\). The index \(j_{1}\) allows to discard the two-dimensional subarrays \(a((1,1,1),\ldots,(n,j_{1},1))\) and \(a((n,i_{1}+1,1),\ldots,(n,n,n))\). The subarrays discarded via index \(i_{2}\) are \(A((1,1,1),\ldots,(i_{2},n,1))\) and \(A((i_{2}+1,n,1),\ldots,(n,n,n))\), as depicted in the Figure 5(b). Each of the other indices, similarly, allows two other two-dimensional subarrays to be discarded. However, in the worst case, there may remain a subarray of each of the original six faces of \(A\). For example, regarding the indices \(j_{1}\) and \(i_{2}\), there remains the subarray \(A((i_{2},j_{1},1),\ldots,(n,n,1))\) within the original face \(A((1,1,1),\ldots,(n,n,1))\), as depicted in the Figure 5(b).