# Searching Monotone Arrays: A Survey
## 3 The Search of Vectors (\(d=1\))
```  
**Algorithm 3** BINARY SEARCH\((A,x)\)  
The discovery of binary search, also known as logarithmic, divide-and-conquer or bisection search, is attributed by [PERSON] [10] to [PERSON] of Uruk in 200 BC. Binary search was mentioned by [PERSON] [13] in what may have been the first published discussion of non-numerical programming methods, but one of the first formal descriptions of it was given by [PERSON] [14]. Furthermore, [PERSON] [15] noted that binary search is also optimal in the average case, as cited by [PERSON] [16]. This history of the evolution of the Binary Search algorithm and its related bibliography, as well as of some other search algorithms listed later here, are described in detail by [PERSON] [10]. [PERSON] [17] also produced an interesting review of the evolution of the binary search design, from an algorithmic point of view. Some of these earlier versions of binary search considered only the case where the length of \(A\) is a power of 2. At that time the method had become well known, but no one appeared to have reported what should be done to accommodate a general \(n\in\mathbb{Z}^{+}\)[15; 18; 19; 20]. It seems that [PERSON] [21] was the first to publish a Binary Search algorithm that worked for all \(n\). [PERSON] [22] provides a detailed analysis of various published versions of the binary search algorithm. In these versions of binary search the position of the central element was calculated and, in the case of fractional values, the position was set to the largest integer smaller than the calculated value. If the sequence contained duplicates of the key value, the first occurrence to the left of the calculated position was found. [PERSON] [23] presented a variation of the algorithm, that is nowadays most common. Setting the position to the smallest integer greater than or equal to the calculated fractional value, the Bottenbruch algorithm adjusts the left pointer, which initially references the first position of the search, to the next position of the central element whenever the key is greater than or equal to this element. Unlike earlier versions, [PERSON]'s algorithm finds the rightmost occurrence of a given key when the sequential search identifies duplicate entries of the key. [PERSON] [24] also proposed a version of binary search for every \(n\in\mathbb{Z}^{+}\), but without considering the possibility of an unsuccessful search. [PERSON] [25] presented the same algorithm as an example of using an automated system for drawing flowcharts. Ternary search [26] (also known as dual-pivot binary search [27]) is a divide and conquer algorithm similar to binary search. In this algorithm, the original array is initially divided into three parts of sizes as close as possible to each other. These segments are usually delimited by positions \(p_{1}=1+\lfloor(n-1)/3\rfloor\) and \(p_{2}=n-\lfloor(n-1)/3\rfloor\) (see the pseudocode in Algorithm 4). By testing the values at these two positions it is possible to discard \(\frac{2}{3}\) of the array and proceed with the same approach on the remaining \(\frac{1}{3}\) of the array. Since a larger portion of the array's elements are discarded, it may appear that ternary search is faster than binary search. In fact, both algorithms have asymptotic time complexity of \(\mathcal{O}(\lg n)\). However, ternary search uses more comparisons than binary search, which adds greater constants to its asymptotic complexity. Similar arguments are also valid for any other similar higher order search algorithms that are generalised from binary search (i.e. \(k\)-nary search, \(k>3\)). Section 7.1 provides some detail on the complexity analysis of \(k\)-nary search. ```
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_{1}\gets i+\left\lfloor\frac{(j-i)}{3}\right\rfloor\);
5:\(p_{2}\gets j-\left\lfloor\frac{(j-i)}{3}\right\rfloor\);
6:if\((x=A[p_{1}])\)then
7:return true. 8:elseif(\(x=A[p_{2}]\))then
9:return true.