/*
  Travis Gadberry
  Patrick Hesser
  Chris Ladewig

  BinarySearch.cpp
  21Mar05
*/


#include "BinarySearch.h"

using namespace std;


BinarySearch::
BinarySearch() {
	n = 1;
	A = new int[n];
	A[0] = 0;
	increments = 0;
	time = 0;
}

BinarySearch::
BinarySearch(int * array, int N) {
	n = N;
	A = new int[n];
	for(int i = 0; i < n; i++)
		A[i] = array[i];
	increments = 0;
	time = 0;
}

BinarySearch::
BinarySearch(const vector<int> V) {
  n = V.size();
  A = new int[n];
  for(int i=0; i<n; i++)
    A[i] = V.at(i);

  increments = 0;
  time = 0;
}

bool 
BinarySearch::
search(int key) {
  time_t t1, t2;
  t1 = clock();
  QuickSort* quick = new QuickSort(A,n);
  quick->sort();
  int * B = quick->getArray();
  bool found = false;

  int low = 0;
  int high = n;

  int mid;

  while((increments++, low <= high) && (increments++, !found)) {
    mid = low+(high-low)/2;
    if(increments++, key==B[mid])
      found = true;         /* found it!             */
    else if(increments++, key<B[mid])
      high = mid-1;         /* search the lower part */
    else               
      low = mid+1;          /* search the upper part */
  }

  t2 = clock();
  time = (t2 - t1)/CLOCKS_PER_SEC;
  return found;
}


int
BinarySearch::
getSearchIncrements() {
  return increments;
}


double
BinarySearch::
getSearchTime() {
	return time;
}