#include <iostream>

using namespace std;

int binarySearch_Iterative(int list[], int size, int key, int* count);
int binarySearch_Recursive(int list[], int start, int stop, int key, int* count);
int linearSearch(int list[], int size, int key, int* count);

int main()
{
   const int NUMEL = 1000000;
   int nums[NUMEL];
   int item, location, count;
   int *searchCount = &count;
   count = 0;
   
   for(int i = 0; i < NUMEL; i++)
      nums[i] = 2 * i;
   
   cout << "Enter the item you are searching for: ";
   cin >> item;
   
   cout << "\nSearching with linearSearch\n";
   location = linearSearch(nums, NUMEL, item, searchCount);
   if (location > -1)
      cout << "The item was found at index location " << location << endl;
   else
      cout << "The item was not found in the list\n";
   cout << "There were " << count << " comparisions\n" << endl;
   *searchCount = 0;
   
   
   cout << "\nSearching with binarySearch_Interative\n" << flush;
   location = binarySearch_Iterative(nums, NUMEL, item, searchCount);
   if (location > -1)
      cout << "The item was found at index location " << location << endl;
   else
      cout << "The item was not found in the list\n";
   cout << "There were " << *searchCount << " comparisions\n" << endl;
   *searchCount = 0;
   
   cout << "\nSearching with binarySearch_Recursive\n";
   location = binarySearch_Iterative(nums, NUMEL, item, searchCount);
   if (location > -1)
      cout << "The item was found at index location " << location << endl;
   else
      cout << "The item was not found in the list\n";
   cout << "There were " << *searchCount << " comparisions\n" << endl;
   
   return 0;
}

int linearSearch(int list[], int size, int key, int* count)
{
   for(int i = 0; i < size; i++)
   {
      *count = *count + 1;
      if (list[i] == key)
         return i;
   }
   
   return -1;
}

// this function returns the location of key in the list
// a -1 is returned if the value is not found
int binarySearch_Iterative(int list[], int size, int key, int *count)
{
   int start, stop, mid;
   
   start = 0;
   stop = size - 1;
   
   while (start <= stop)
   {
      *count = *count + 1;
      mid = (int) ((start + stop) / 2);
      if (key == list[mid])
         return mid;
      else if (key > list[mid])
         start = mid + 1;
      else
         stop = mid - 1;
   }

   return -1;
}

// recursive binary search
int binarySearch_Recursive(int list[], int start, int stop, int key, int* count)
{ 
   int mid = (start + stop ) / 2;
   *count = *count + 1;
   if (stop < start)
      return(-1);
   else if (list[mid] == key)
      return(mid);
   else if (list[mid] < key)
      return( binarySearch_Recursive(list, mid + 1, stop, key, count) );
   else if (list[mid] > key)
      return( binarySearch_Recursive(list, start, mid-1, key, count) );
}