I thought binary search was just good for sorted arrays, but this article on TopCoder was really good. It got me thinking of all sorts of ways to avoid a linear search when you know a search space has an inflection point that can be tested with a predicate.

Here's my humble implementations of binary search (it's burned into my brain):

``````int binary_search(int target, int numbers[], int size) {
int low = 0;
int high = size - 1;
int mid = 0;
while (low <= high) {
mid = (high + low) / 2;

if (target > numbers[mid]) {
low = mid + 1;
} else if (target < numbers[mid]) {
high = mid - 1;
} else {
return mid;
}
}

return -1;
}

int binary_search_recur(int target, int numbers[], int low, int high) {
if (low > high) {
return -1;
}

int mid = (high + low) / 2;

if (target > numbers[mid]) {
return binary_search_recur(target, numbers, mid + 1, high);
} else if (target < numbers[mid]) {
return binary_search_recur(target, numbers, low, mid - 1);
} else {
return mid;
}
}
``````
comments powered by Disqus