Programming Pearls 2nd Edition: Column 5: Binary Search

binary_search.c

/*
 * Programming Pearls 2nd Edition
 * Column 5: Binary Search
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>


/* --------------------------------------------------------
   Binary Search
   -------------------------------------------------------- */
typedef int DataType;

static int binarysearch(DataType t, DataType *seq, size_t n) {
  int l = 0, u = n - 1;

  while(l <= u) {
    int m = (l + u) / 2;
    int v = seq[m];

    if (t == v) {
      assert(m >= 0 && m < n && seq[m] == t);
      return m;
    }
    if (t > v) l = m + 1;
    else u = m - 1;
  }
  assert(l > u);
  return -1;
}


/* --------------------------------------------------------
   Test
   -------------------------------------------------------- */
static void test_binarysearch(size_t max) {
  DataType *seq = malloc(sizeof(DataType) * max);
  int i, p;

  assert( seq != NULL && "malloc error");
  for (i = 0; i < max; i++) seq[i] = i * 10;

  /*printf("Running autotest for %u size...\n", max);*/
  for (i = 0; i < max; i++) {
    p = binarysearch(i * 10, seq, max);
    assert( p == i );
    p = binarysearch(i * 10 + 1, seq, max);
    assert( p == -1 );
  }
  
  p = binarysearch(10 * max + 5, seq, max);
  assert( p == -1 );
  p = binarysearch(10 * max, seq, max);
  assert( p == -1 );
  /*printf("OK\n");*/
  free(seq);
}


/* --------------------------------------------------------
   Profile
   -------------------------------------------------------- */
static void profile_binarysearch(size_t n, size_t num_tests) {
  DataType *x = malloc(sizeof(DataType) * n);
  int i, p, testnum;
  clock_t starttime, elapsed;

  assert( x != NULL && "malloc error");
  for (i = 0; i < n; i++) x[i] = i;

  starttime = clock();
  for (testnum = 0; testnum < num_tests; testnum++) {
    for (i = 0; i < n; i++) {
      p = binarysearch(i, x, n);
      assert( p == i );
    }
  }
  elapsed = (clock() - starttime);
  free(x);

  printf("n=%u (%u times): %lu clocks, %.3f msec/cycle\n",
    n, num_tests, elapsed,
    ((double)elapsed/(CLOCKS_PER_SEC * num_tests * n))*1000);
}

/* --------------------------------------------------------
   Main
   -------------------------------------------------------- */
static DataType x[] = {1, 3, 6, 7, 9, 12, 66, 70, 71};

static void try_binarysearch(DataType t) {
  size_t size = (sizeof(x)/sizeof(x[0]));
  int p = binarysearch(t, x, size);

  printf("Searching: %d\n", t);
  printf("Result: %d\n", p);
}

int main(void) {
  int i;
  size_t size = (sizeof(x)/sizeof(x[0]));

  printf("[");
  for (i = 0; i < size; i++) {
    printf("%d", x[i]);
    if (i < (size - 1)) printf(", ");
  }
  printf("]\n");

  try_binarysearch(9);
  try_binarysearch(66);
  try_binarysearch(1);
  try_binarysearch(71);
  try_binarysearch(10000);
  try_binarysearch(-999);

  for (i = 0; i <= 100; i++) test_binarysearch(i);

  printf("\n\n");
  profile_binarysearch(1000, 10000);
  profile_binarysearch(10000, 1000);
  profile_binarysearch(100000, 100);
  profile_binarysearch(1000000, 10);
  return 0;
}