/*
   testsearch3.cpp
   CIS 150
   David Klick
   6/24/08
   
   Comparison of linear and binary searches.
*/

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

const int ARRAY_SIZE = 100000;

int lsearch(int n[], int len, int key);
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;
   clock_t startTime, stopTime;
   double elapsedTime;
   int hits, misses;

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

   // array must be sorted for binary search
   cout << "Sorting array...";
   sort_array(nums, ARRAY_SIZE);

   // do linear search for 100,000 random values
   hits = 0; misses = 0;
   cout << "\nConducting linear searches\n";
   startTime = clock();
   for (i=0; i<100000; i++) {
      val = rand() % 1000000;
      pos = lsearch(nums, ARRAY_SIZE, val);
      if (pos != -1) hits++;
      else misses++;
   }
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   cout << "Hits: " << hits << ", Misses: "
        << misses << " (" << elapsedTime << " ms)\n";
   
   // do binary search for 100,000 random values
   hits = 0; misses = 0;
   cout << "\nConducting binary searches\n";
   startTime = clock();
   for (i=0; i<100000; i++) {
      val = rand() % 1000000;
      pos = bsearch(nums, ARRAY_SIZE, val);
      if (pos != -1) hits++;
      else misses++;
   }
   stopTime = clock();
   elapsedTime = difftime(stopTime, startTime);
   cout << "Hits: " << hits << ", Misses: "
        << misses << " (" << elapsedTime << " ms)\n";
   
   cont();
   return 0;
}

/*
   int lsearch(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 do NOT have to be in sorted order.
   Returns position where key value was found in n[].
   Returns -1 if key value not found in n[].
*/
int lsearch(int n[], int len, int key) {
   int i;
   for (i=0; i<len; i++) {
      if (n[i] == key) return i;
      if (n[i] > key) break;
   }
   return -1;
}

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

   Sorting array...
   Conducting linear searches
   Hits: 95164, Misses: 4836 (25266 ms)

   Conducting binary searches
   Hits: 95126, Misses: 4874 (31 ms)

   Sample output:

   Sorting array...
   Conducting linear searches
   Hits: 95283, Misses: 4717 (25453 ms)

   Conducting binary searches
   Hits: 95388, Misses: 4612 (47 ms)   
*/