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

Note:Its always safe to choose the mid point by taking mid=left + (right-left)/2 because it prevents the overflow when the array index is large and both right and left fall near the highest index

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 := left+floor((right-left) / 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-l) / 2;
        if (a[c] > x)
            r = c - 1;
        else if (a[c] < x)
            l = c + 1;
        else
            return c;
    }
    return -1;
}