// ---------------------------------------------------------------------------
// BinarySearch.C
//
// A simple implementation of binary search for C++ using a template class
//
// Paul McNamee
// Introduction to C++ Programming, 605.201, 8/97
// ---------------------------------------------------------------------------

// ---------------------------------------------------------------------------
// Binary search is an algorithm for searching ordered sets that can
// "find" in O(lg N), time logrithmic to the cardinality of the set
// instead of the O(N), linear time required if every element in the
// set is compared.  This class assumes the templated class provides
// an operator < for comparisons and an operator ==.

#include <iostream.h>

template <class T>
class BinarySearch {
  public :
    T *array;
    BinarySearch (T *a) {
      array = a ;  // Note this does not copy the array, it merely sets pointer!
    }

    // Find x in the array, or return -1 for failure!  Call the
    // other Find function for results
    int Find (T x, int maxlen) {
      return Find(x, 0, maxlen-1);
    }

    // The Binary search function
    int Find (T x, int lo, int hi) {
      cout << "In Find, lo is " << lo << " and hi is " << hi << endl;
      if (array[lo] == x) {
        return lo;
      } else if (array[hi] == x) {
        return hi;
      } else if (hi <= lo+1) {
        return -1;
      } else {
        int mid = (int) ((hi+lo)/2);
        int res;
        if (x < array[mid])
          res = Find(x, lo, mid);
        else
          res = Find(x, mid, hi);
        return res;
      }
    }
} ;


// ---------------------------------------------------------------------------
// BinarySearch.C (cont'd)

int main () {
  int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 27};
  BinarySearch<int> bsi(primes) ;

  cout << "Test #1.  Will fail since 13 isn't in first 4 primes\n" ;
  int nope = bsi.Find(13, 4);
  cout << "Test #1.  Result is " << nope << endl;
  
  cout << "Test #2.  Will work since 13 is prime\n" ;
  int yep = bsi.Find(13, 10);
  cout << "Test #2.  Result is " << yep << endl;
  
  return 1;
}

// ---------------------------------------------------------------------------
// Some output:
// paulmac@nautilus: CC -o BinarySearch BinarySearch.C
// paulmac@nautilus: BinarySearch
// Test #1.  Will fail since 13 isn't in first 4 primes
// In Find, lo is 0 and hi is 3
// In Find, lo is 1 and hi is 3
// In Find, lo is 2 and hi is 3
// Test #1.  Result is -1
//
// Test #2.  Will work since 13 is prime
// In Find, lo is 0 and hi is 9
// In Find, lo is 4 and hi is 9
// In Find, lo is 4 and hi is 6
// In Find, lo is 5 and hi is 6
// Test #2.  Result is 5
// paulmac@nautilus: