Recursive Binary Search

2020-08-15

Binary search is a search algorithm that operates on sorted sequences of data. This blog post will present one possible implementation of recursive binary search algorithm, walks through its details, and expresses the algorithm in C++.

Pseudocode for one possible recursive binary search algorithm is

\begin{algorithm}
\caption{\textsc{Binary-Search}$(A, key)$}
\begin{algorithmic}
\State $i = \lfloor A\text{.length} \ / \ 2 \rfloor$
\State $L = A[1 \ \ldots \ i]$
\State $R = A[i + 1 \ \ldots \ A\text{.length}]$
\If{ $ key \ != A[i] $ }
    \If{ $L\text{.length} == 0$ }
        \Return $\infty$
    \ElseIf{ $key < A[i]$ }
        \Return \textsc{Binary-Search}($L, \ key$)
    \Else
        \Return \textsc{Binary-Search}($R, \ key$)
    \EndIf
\Else
    \Return $A[i]$
\EndIf
\end{algorithmic}
\end{algorithm}

where \( A \) is assumed to be a partial order array, that is, an array satisfying the property, \[ A = \{ \ a_i \in A \ | \ a_1 \leq a_2 \leq \ldots \leq a_i \ \} \] and \( key \) is a value to be searched from \( A \).

Binary search begins by assigning a rounded down index value for variable \( i \) that indexes middle of the argument array \( A \), which is then split into left and right subarrays, named \( L \) and \( R \) respectively.

After initial setup, the reason of the algorithm is fulfilled at line \( 4 \) when \( key \) is tested with respect to value at \( A[i] \). If the two terms are not equal, and length of \( A \) is not zero, anew recursive query is done either into \( L \) or \( R \). The path chosen is dependant on whether the predicate \( key < A[i] \) is true or not. That is, left subarray is searched if \( key \) is less than value at \( A[i] \), right otherwise.

Algorithm returns the value of positive infinity if \( key \) is not in \( A \). This return value was chosen, so that the algorithm can be used to construct further algorithmic expressions which evaluate numerical values rather than booleans.

Binary search as described above can be expressed in C++ as follows:

template <typename T>
T binary_search(const std::vector<T>& vector, const T& key)
{
    T i = vector.size() / 2; 
    T candidate = vector.at(i);

    std::vector<T> L {vector.begin(), vector.begin() + i},
                   R {vector.begin() + i, vector.end()};

    if (key != candidate)
    {
        if (L.size() == 0)
            return std::numeric_limits<T>::infinity;
        else if (key < candidate)
            return binary_search(L, key);
        else
            return binary_search(R, key);
    }

    else return candidate;
}

The program is syntactically identical to the presented algorithm, with the exception that \( A[i] \) is being assigned into variable candidate in order to improve readability.

References:

Cormen, T. H., Leiserson, E. C., Rivest, R. L, and Stein, C. 2009. Introduction to algorithms. 3rd ed. Cambridge: The MIT Press.