Skip to content

Instantly share code, notes, and snippets.

/bsearch.d

Created Apr 19, 2010
Embed
What would you like to do?
/**
* 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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment