bsearch.d

/**
 * An implementation of the binary search algorithm for
 * http://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
 */
module bsearch;


/**
 * Performs a binary search over list 'l' for element 'e'.
 * Returns the index, or -1 on failure.
 *
 * 'base' is for internal use by the function.
 *
 * The return value should be size_t, but we are allowed to ignore overflow.
 */
int bsearch(T)(T[] l, T e, int base = 0)
{
    int index(int i)
    {
        return base + i;
    }

    if (l.length == 0) return -1;
    if (l.length == 1) {
        if (l[0] == e) {
            return index(0);
        } else {
            return -1;
        }
    }

    size_t mid = l.length / 2;
    if (e == l[mid]) {
        return index(mid);
    } else if (e < l[mid]) {
        return bsearch(l[0 .. mid], e, 0 + base);
    } else if (e > l[mid]) {
        return bsearch(l[mid .. $], e, mid + base);
    }

    // We shouldn't reach here.
    assert(false);
}


void main()
{
}


unittest
{
    int[] l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    assert(bsearch(l, 5)  == 4);
    assert(bsearch(l, 1)  == 0);
    assert(bsearch(l, 10) == 9);
    assert(bsearch(l, 11) == -1);
    assert(bsearch(l, 0)  == -1);
    
    int[] ll = [5];
    assert(bsearch(ll, 5) == 0);
    assert(bsearch(ll, 6) == -1);
    assert(bsearch(ll, 4) == -1);
    ll ~= 6;
    assert(bsearch(ll, 5) == 0);
    assert(bsearch(ll, 6) == 1);
    assert(bsearch(ll, 7) == -1);
    assert(bsearch(ll, 4) == -1);

    int[] z = [];
    assert(bsearch(z, 1) == -1);
}