/*
   testsearch2.cpp
   CIS 150
   David Klick
   6/28/05
   
   Demonstration of binary search.
*/

#include <iostream>
#include <cstdlib>
#include <ctime>
using std::cout;

const int ARRAY_SIZE = 10;

int bsearch(int n[], int len, int key);
void sort_array(int n[], int len);

int main(void) {
   int nums[ARRAY_SIZE];
   int i, val, pos;

   // randomize random number generator
   srand(time(NULL));
   
   // fill array up with random ints (0-99)
   for (i=0; i<ARRAY_SIZE; i++) {
      nums[i] = rand() % 100;
   }

   // array must be sorted for binary search
   sort_array(nums, ARRAY_SIZE);
   
   // display array
   for (i=0; i<ARRAY_SIZE; i++) cout << nums[i] << ' ';
   cout << '\n';
   
   // search for 10 random values
   for (i=0; i<10; i++) {
      val = rand() % 100;
      pos = bsearch(nums, ARRAY_SIZE, val);
      if (pos != -1) {
         cout << val << " found at position " << pos << '\n';
      } else {
         cout << val << " not found\n";
      }
   }
   
   return 0;
}

/*
   bsearch(int n[], int len, int key)
   
   performs binary search of array n[] for value: key
   len must be set to size of n[] array
   the array values must be in sorted order
   
   returns position where key value was found in n[]
   returns -1 if key value not found in n[]
*/
int bsearch(int n[], int len, int key) {
   int lo=0, hi=len-1;
   int mid;
   while (lo <= hi) {
      mid = (lo+hi) / 2;
      if (n[mid] > key) hi = mid - 1;
      else if (n[mid] < key) lo = mid + 1;
      else return mid;
   }
   return -1;
}

// sorts array n[] into ascending order
void sort_array(int n[], int len) {
   int i, j, tmp;
   for (i=0; i<len-1; i++) {
      for (j=i+1; j<len; j++) {
         if (n[i] > n[j]) {
            tmp = n[i];
            n[i] = n[j];
            n[j] = tmp;
         }
      }
   }
}

/*
   Sample output
   
   13 15 27 33 36 50 51 54 89 90
   1 not found
   15 found at position 1
   47 not found
   95 not found
   40 not found
   60 not found
   54 found at position 7
   55 not found
   78 not found
   66 not found
*/