/*
   search.cpp
   David Klick
   CIS 250
   1/31/05

   demonstration of linear and binary search
*/
#include <iostream>
#include <cstdlib>
#include <ctime>
using std::cout;
using std::endl;

const int SIZE = 40000;

void quickSort(int*, int);
void q_sort(int*, int, int);
int linsearch(int, int*, int);
int binsearch(int, int*, int);

int main(void) {
   int num[SIZE];
   int i, hits, misses;
   srand(time(NULL));

   // create array of random ints (not in order)
   // note: some compilers will not allow ints this large
   for (i=0; i<SIZE; i++) num[i] = rand() % 100000;

   // now search for every even integer with linear search
   cout << "Linear search started" << endl;
   hits = misses = 0;
   for (i=0; i<100000; i+=2) {
      if (linsearch(i, num, SIZE) == -1) misses++;
      else hits++;
   }
   cout << "Linear search: hits=" << hits << ", misses="
        << misses << "\n\n";

   // data must be sorted for binary searches
   cout << "Binary search started" << endl;
   quickSort(num, SIZE);

   // now search for every even integer with binary search
   hits = misses = 0;
   for (i=0; i<100000; i+=2) {
      if (binsearch(i, num, SIZE) == -1) misses++;
      else hits++;
   }
   cout << "Binary search: hits=" << hits << ", misses="
        << misses << "\n\n";

   return 0;
}

int linsearch(int k, int* arr, int len) {
   for (int i=0; i<len; i++) {
      if (k == arr[i]) return i;
   }
   return -1;
}

int binsearch(int k, int* arr, int len) {
   int hi = len - 1;
   int lo = 0;
   int middle;
   while (hi >= lo) {
       middle = (hi + lo) / 2;
       if (arr[middle] == k) return middle;
       else if (arr[middle] > k) hi = middle - 1;
       else lo = middle + 1;
   }
   return -1;
}

void quickSort(int a[], int len) {
   q_sort(a, 0, len-1);
}

void q_sort(int a[], int left, int right) {
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = a[left];
   while (left < right) {
       while ((a[right] >= pivot) && (left < right)) right--;
       if (left != right) a[left++] = a[right];
       while ((a[left] <= pivot) && (left < right)) left++;
       if (left != right) a[right--] = a[left];
   }
   a[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot) q_sort(a, left, pivot-1);
   if (right > pivot) q_sort(a, pivot+1, right);
}