Binary Search

From Algorithmist

Binary Search searches by exploiting the ordering in a sequence in splitting it in half each time.

A real-life example of Binary Search would be if you were to look for the name "Larry" in a phonebook, you would first go to the middle of the phonebook, if "Larry" is before the middle entry, you rip and throw away the latter half, and then do the same thing.

Binary Search is an example of divide and conquer paradigm. It runs in O(logn) time on an array of length n.

[edit] Pseudo-code

Recursively:

/* Searches value 'x' in sorted array a[left], a[left+1], ..., a[right].
   Returns the index of 'x' in array, or -1 if it cannot be found. */
search(a, left, right, x)
    if left > right then
        return -1
    mid := floor((left + right) / 2)
    if a[mid] = x then
        return mid
    else if a[mid] > x then
        return search(a, left, mid-1, x)
    else
        return search(a, mid+1, right, x)

Iteratively (in C):

/* Search value 'x' in array a[0],a[1],...,a[n-1] */
int search(int a[], int n, int x)
{
    int l, r, c;
    for (l = 0, r = n-1; l <= r;) {
        c = (l + r) / 2;
        if (a[c] > x)
            r = c - 1;
        else if (a[c] < x)
            l = c + 1;
        else
            return c;
    }
    return -1;
}