/*
   testsearch2.cpp
   CIS 150
   David Klick
   6/24/08
   
   Demonstration of binary search.
*/

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

const int ARRAY_SIZE = 10;

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

int main() {
   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";
      }
   }
   
   cont();
   return 0;
}

/*
   int bsearch(int n[], int len, int key);
   
   Arguments:
      int n[]: array of integers to be searched
      int len: number of elements in array
      int key: value being searched for in array

   Returns: The position of the key value within the array
      if found, or -1 if not found.

   Performs linear search of array n[] for value: key.
   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;
}

/*
   void sort_array(int n[], int len);
   
   Arguments:
      int n[]: array of integers to be sorted
      int len: number of elements in array

   Returns: nothing (but a side effect is that the array
      passed in is put into ascending sorted order)

   Sorts the integer array n[] into ascending order.
   This is a very inefficient sort and should not be used
   for real-world problems.
*/
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;
         }
      }
   }
}

/*
   void cont();
   
   Arguments: none
   
   Returns: nothing
   
   Clears input buffer and pauses waiting for user 
   to press Enter.
*/
void cont() {
   if (cin.rdbuf()->sungetc() != -1 && cin.get() != '\n') cin.ignore(80,'\n');
   cout << "Press enter to continue...";
   cin.get();
}

/*
   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
*/