# Searching Monotone Arrays: A Survey
## 3 The Search of Vectors (\(d=1\))  
When \(d=1\) and \(n_{1}=n\) say, \(A\) is a monotone vector (a totally ordered set). Many of the monotone vector search methods mentioned below are based on comparisons of keys and have been described in detail by [PERSON] [10]. The Linear (or Sequential) Search algorithm (see the pseudocode in Algorithm 1) is a basic method for finding a key within \(A\), whether \(A\) is ordered or not. The algorithm starts at the leftmost element of \(A\) and iteratively compares the key \(x\) with each element of \(A\). The search stops when either \(x\) matches an element of \(A\) or when all the elements have been tested. Its running time and number of comparisons are, in the worst case, linear in \(n\). ```
0: Array \(A(1,\ldots,n)\) and key \(x\in\mathbb{R}\). 0: True if \(x\in A\) or False otherwise. 1:\(i\gets 1\);
2 while(\(i\leqslant n\)) do
3:if\((x=A[i])\)then
4:return true. 5:else
6:\(i\gets i+1\);
7:endif
8:endwhile
9:return false. ```  
**Algorithm 1** LINEAR\(\text{SEARCH}(A,x)\)  
The Jump Search algorithm [11], also known as Block Search [12], check fewer elements of an ordered array \(A(1,\ldots,n)\) than the Linear Search, by jumping ahead blocks of a fixed number \(m\) of elements. It verifies the elements of \(A\) in the indexes \(1,1+m,1+2m,\ldots,1+km\). Once is determined that \(A[1+(k-1)m]<x<A[1+km]\), a linear search is done in the interval \((1+(k-1)m,1+km)\) to check if any of these elements is equal the key \(x\). Its pseudocode is shown in Algorithm 2. [PERSON] [11] shown that the optimal value of the jump size is \(m=\sqrt{n}\). Therefore, if the cost of a jump is \(c_{j}\), and the cost of a sequential search is \(c_{s}\), then the optimum jump size is \(\sqrt{(c_{j}/c_{s})n}\) and the search cost is \(\tau(n,1)=\sqrt{(c_{j}c_{s})n}\). [PERSON] also describes some variations of this algorithm, as the multi-level jumping or the variable jump size. Jump Search traverses the array back only once, that can be an advantage in situations where jumping back is costly. Note that Binary Search (the next described algorithm), in the worst case, may require up to \(\mathcal{O}(\log n)\) back jumps! The Binary Search algorithm begins with the vector \(A\) as the initial search interval, and repeatedly divides the current search interval into two parts that are either of the same length or differ in length by one unit. If the key \(x\) is lower than the entry in the \"middle\" position of the interval (this situation is depicted in Figure 2, where \(p\) is the \"middle\" position), the search space is narrowed to its lower half (positions 1 to \(p-1\)). If the key \(x\) is greater than the mentioned entry, the interval it is narrowed to the upper half (positions \(p+1\) to \(n\)). The pseudocode of binary search is given in Algorithm 3. It is straightforward to show that the asymptotic complexity of this version of the algorithm is  
\[\tau(n,1)=2\lfloor\log(n)\rfloor+1=\mathcal{O}(\log(n)). \tag{8}\]  
However, it is not strictly necessary to compare the key \(x\) with the element at position \(p\) at each iteration of the search loop. An alternative approach, also commonly used, just checks to see if \(x\
eq p\). If this is not so, \(p\) is returned and the procedure is terminated. Otherwise, \(p\) is retained in the search space, which will eventually shrink to \(p\) when \(p=x\). However, after exiting the loop, i.e., after the search space is completely exhausted, it is necessary to compare the final element in the space with \(x\). The asymptotic implications of assuming that each iteration requires only one comparison are explored in Section 7.1. Figure 2: Binary search vector bisection. ```
0: Array \(A(1,\ldots,n)\) and key \(x\in\mathbb{R}\). 0: True if \(x\in A\) or False otherwise. 1:\(i\gets 1\);
2:\(j\gets n\);
3:while(\(i\leqslant j\)) do
4:\(p\leftarrow\lfloor\frac{i+j}{2}\rfloor\);
5:if(\(x=A[p]\)) then
6:return true;
7:elseif(\(x<A[p]\)) then
8:\(j\gets p-1\);
9:else
10:\(i\gets p+1\);
11:endif
12:endwhile
13:return false.