Binary Search

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;
  }
}