# Searching Monotone Arrays: A Survey
## 3 The Search of Vectors (\(d=1\))
10:elseif(\(A[p_{1}]>x\))then
11:\(j\gets p_{1}-1\);
12:elseif(\(A[p_{2}]<x\))then
13:\(i\gets p_{2}+1\);
14:else
15:\(i\gets p_{1}+1\);
16:\(j\gets p_{2}-1\);
17:endif
18:endwhile return false. ```  
**Algorithm 4** TERNAY SEARCH\((A,x)\)  
The Interpolation Search algorithm, due to [PERSON] [28], performs similarly to binary search but unlike it, which always checks the intermediate element of the search space, the interpolation search can check different elements according to the value of the key and the statistical distribution of the elements in the array \(A\). For example, it is likely that the interpolation search will start at an element either near the index \(n\) (when the key is closer to \(A[n]\)), or near the index \(1\) (when the key is closer to \(A[1]\).) The pseudocode is shown in Algorithm 5. When the values in the array \(A\) are uniformly distributed, the interpolation search has a performance superior of that of binary search. [PERSON] et al. [29] showed that this algorithm requires on the average \(\log\log n\) array accesses to check if a key is present in the array, assuming that the \(n\) array entries are uniformly distributed. The Exponential Search algorithm is attributed to [PERSON] and [PERSON] [30]. This search algorithm involves a preliminary step of finding a small range of elements of the array \(A\) (potentially containing the key \(x\)) and a secondary step of performing a binary search in this limited range of elements. The first step starts with a subarray of size \(1\), compares its unique element with the key \(x\), then, if necessary, compares a subarray of size \(2\), then of \(4\), and so on, until the last element, index \(i\) say, of the current subarray is not greater than the key \(x\). At the end of this step, the key can only be present between the indexes \(i/2\) and \(i\). Therefore, a binary search is carried out in this range. The pseudocode of this algorithm is shown in Algorithm 6. Exponential Search is particularly useful for unbounded arrays, that is, where the size of the array to be searched is infinite. This search also works better than binary search for bounded arrays when the key \(x\) is closer to the first element of the array. ```
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)\) and \((A[i]\
eq A[j])\) and \((A[i]\leqslant x\leqslant A[j])\)do
4:\(p\gets i+\left[\frac{(j-i)}{(A[j]-A[i])}\right]\cdot(x-A[i])\);
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:if\((i\leqslant n)\) and \((A[i]=x)\)then
14:return true
15:else
16:return false. 17:endif
```  
**Algorithm 5** INTERPOLATION SEARCH\((A,x)\)  
```
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:if\((x=A[i])\)then
3:return true. 4:endif
5:while\((i\leqslant n)\) and \((x>A[i])\)do
6:\(i\gets i\cdot 2\);
7:endwhile
8:return BINARY SEARCH\((A(\lfloor\frac{i}{2}\rfloor+1,\min\{i,n\}),x)\). ```  
**Algorithm 6** EXPONENTIAL SEARCH\((A,x)\)  
Fibonacci Search (Ferguson [31]) splits the array \(A\) into two subarrays with sizes that are consecutive Fibonacci numbers, which are defined as:  
\[F_{m}= \begin{cases}m,&\text{if }0\leqslant m<2;\\ F_{m-1}+F_{m-2},&\text{if }m\geqslant 2.\end{cases}  \tag{9}\]  
This search first finds the smallest Fibonacci number, the \(m^{th}\) one say, greater than or equal to \(n\), then uses the \((m-2)^{th}\) Fibonacci number as the index of the array element to be compared with the key (if it is a valid index). While there are still elements to be inspected, the limits of the subarray that must be searched are calculated based on the three consecutive Fibonacci numbers currently used. The pseudocode shown in Algorithm 7, uses the \(m^{th}\) Fibonacci number just defined and a variable offset to help to discard the unnecessary positions of the array \(A\). ```
0: Array \(A(1,\ldots,n)\) and key \(x\in\mathbb{R}\).