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

#include <iostream>
#include <cstdlib>
#include <ctime>
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);

int main(void) {
   int nums[ARRAY_SIZE];
   int i, val, pos;
   clock_t startTime, stopTime;
   double elapsedTime;
   int hits, misses;

   // randomize random number generator
   srand(time(NULL));
   
   // 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";
   
   return 0;
}

/*
   lsearch(int n[], int len, int key)
   
   performs linear search of array n[] for value: key
   len must be set to size of n[] array
   the array values do NOT have to be in sorted order
   (but since they are in this case, we can adjust the
   code slightly to speed things up)
   
   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;
}

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

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