How To: Sort and Search Arrays, Fast!

//////////////////////////////////
// Robert Burns, Diablo Valley College
// February 5, 2003
//
// Fast Sorting and Searching Arrays:
//  a sample with ints and classes

#include <cstdlib>

class tod
{
  public:
  int hour;
  int minute;
  int second;
};

// prototypes for sort functions
int binarySearchInt(const int, const int[], const int); // for int arrays
int binarySearchTod(const tod, const tod[], const int); // for tod arrays

// prototypes for compare functions
int compareInt(const void*, const void*); // for ints
int compareTod(const void*, const void*); // for tods

int main()
{
  // a sample with ints
  {
    // create an unsorted array
    const int N = 10; // array size
    int a[N] = {3,6,1,2,8,9,4,3,12,0};

    // sort the array w/built-in C function
    qsort(a, N, sizeof(int), compareInt);

    // see if array contains some specified value
    int matchMe = 9; // this one's in the array
    int found = 0; // assume it's not in the array
    if (binarySearchInt(matchMe, a, N) == 0)
      found = 1; // it's found
  }

  // a sample with structs
  {
    // create an unsorted array
    const int N = 4; // array size
    tod a[N] = {{12,0,0},{15,30,0},{2,10,50},{4,0,0}};

    // sort the array w/built-in C function
    qsort(a, N, sizeof(tod), compareTod);

    // see if array contains some specified value
    tod matchMe = {15,30,0}; // this one's in the array
    int found = 0; // assume it's not in the array
    if (binarySearchTod(matchMe, a, N) == 0)
      found = 1; // it's found
  }
  return 0;
}

///////////////////////////////////////////////
// functions for comparing -- return a negative
//  number if pa precedes pb, positive if pa
//  follows pb, and zero if they are the same
int compareInt(const void* pa, const void* pb)
{
  // convert argument variables into something recognizable
  const int& a = *static_cast<const int*>(pa);
  const int& b = *static_cast<const int*>(pb);

  // compare ints
  if (a < b) return -1;
  if (a > b) return 1;
  return 0;
}

int compareTod(const void* pa, const void* pb)
{
  // convert argument variables into something recognizable
  const tod& a = *static_cast<const tod*>(pa);
  const tod& b = *static_cast<const tod*>(pb);

  // compare tods
  if (a.hour < b.hour) return -1;
  if (a.hour > b.hour) return 1;

  if (a.minute < b.minute) return -1;
  if (a.minute > b.minute) return 1;
  
  if (a.second < b.second) return -1;
  if (a.second > b.second) return 1;
  return 0;
}

//////////////////////////////////////////////
// functions for searching
// "a" is a SORTED array with N elements
// return 0 if any element in "a" matches "lookForThis"
// return 1 otherwise
int binarySearchInt(const int lookForThis, const int a[], const int N)
{
  int low = 0;
  int high = N - 1;

  while(low <= high)
  {
    int mid = (low + high) / 2;
    int cmp = compareInt(&a[mid], &lookForThis);
    if(cmp < 0)
      low = mid + 1;
    else if(cmp > 0)
      high = mid - 1;
    else
      return 0; // converged on value at index "mid"
  }
  return 1; // did not find
}

int binarySearchTod(const tod lookForThis, const tod a[], const int N)
{
  int low = 0;
  int high = N - 1;

  while(low <= high)
  {
    int mid = (low + high) / 2;
    int cmp = compareTod(&a[mid], &lookForThis);
    if(cmp < 0)
      low = mid + 1;
    else if(cmp > 0)
      high = mid - 1;
    else
      return 0; // converged on value at index "mid"
  }
  return 1; // did not find
}