Binary Search

Given as input an integer x and a vector v of integers ordered increasingly, i.e. v[0]\leq v[1]\leq v[2]\leq \cdots, return the position of x if it appears in the vector v (and -1 otherwise).

The fact that the vector is of integers is not relevant, obviously, it could be of elements of any type T, as long as T has defined an ordering on it.

template <class T>

// Initial call: int p = BinarySearch(v, 0, v.size() - 1, x);

int BinarySearch(const vector<T>& v, int left, int right, T x){
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (x < v[mid]) 
        return BinarySearch(v, left, mid - 1, x);
    if (x > v[mid]) 
        return BinarySearch(v, mid + 1, right, x);
    return mid;
}

First occurrence?

Does the code above find the first occurrence of x in v? If not, how can you modify it so that it does?

You might want to solve the Jutge.org exercise P84219 First occurrence.

The worst case running time T(n) of BinarySearch on an input of size n satisfies the recurrence

T(n)=T\left(\frac{n}{2}\right)+\Theta(1)

which, by the Master Theorem, gives T(n)=\Theta(\log n).

This is actually the best possible among all comparison-based search algorithms. A comparison-based search algorithm, searching for an element x in a vector v, is only allowed to interact with v by asking questions of the form

“is x>v[i]?” or
“is x=v[i]?”, or
“is x < v[i]?”,

and getting a YES/NO answer.

Theorem

Any deterministic comparison-based searching algorithm must perform \Omega(\log n) comparisons in the worst case to search for an element in a vector of size n.

The proof of the theorem above is similar to the one used to show the lower bound on the \Omega(n\log n) worst case running time of any comparison-based sorting algorithm, and it is left as an exercise.

Other Links