//Sam Partovi                      CS1A                     Chapter 8, P 488, #8
//
/*******************************************************************************
* COMPARE SEARCH ALGORITHM EFFICIENCY
* ____________________________________________________________
* This program compares the efficiencies of linear and binary search algorithms
* by searching through an array of specified values and counting the number of 
* comparisons needed for each algorithm to complete the search.
* ____________________________________________________________
*INPUT
* ARRAY_SIZE: Size of array to be searched
* targetValue: Given number to be located in array
* array: Array of numbers to be searched
*OUTPUT
* linearCounter: Counter for linear search comparisons
* binaryCounter: Counter for binary search comparisons
* linearResult:  Index of number found via linear search
* binaryResult:  Index of number found via binary search
******************************************************************************/
#include <iostream>
#include <iomanip>
using namespace std;

const int ARRAY_SIZE = 20;   //INPUT - Size of array to be searched

int LinearSearch(const int, int, int[], int&);
int BinarySearch(const int, int, int[], int&);

int main() {
 int targetValue = 3000;    //INPUT - Given number to be located in array

//INPUT - Array of numbers to be searched
 int array[ARRAY_SIZE] = {124, 125, 163, 168, 182, 185, 195, 204, 206, 209, 785,
                          858, 915, 1592, 1597, 2000, 2005, 2025, 2090, 3000};
                          
 int linearCounter = 0;     //OUTPUT - Counter for linear search comparisons
 int binaryCounter = 0;     //OUTPUT - Counter for binary search comparisons
 int linearResult;          //OUTPUT - Index of number found via linear search
 int binaryResult;          //OUTPUT - Index of number found via binary search

//Call LinearSearch function
 linearResult = LinearSearch(ARRAY_SIZE, targetValue, array, linearCounter);

//Display linear search results
 cout << "LINEAR SEARCH: Number is in index " << linearResult;
 cout << "\nTook " << linearCounter << " comparisons";
 
//Format output
 cout << "\n-----------------------------------\n";
 
//Call BinarySearch function
 binaryResult = BinarySearch(ARRAY_SIZE, targetValue, array, binaryCounter);
 
//Display binary search results
  cout << "BINARY SEARCH: Number is in index " << binaryResult;
  cout << "\nTook " << binaryCounter << " comparisons\n";
  
 //Determine the most efficient search algorithm
  if(linearCounter < binaryCounter) {
  	cout << "\nThe linear search is more efficient in this case.";
  }
  else if(linearCounter == binaryCounter) {
  	cout << "\nLinear and binary searches are equally efficient in this case.";
  }
  else cout << "\nThe binary search is more efficient in this case.";
  
return 0;
}

//******************************************************************************
//Definition for LinearSearch function:
// This function performs a linear search on the given array and returns the
// index of the targetValue and counts the number of comparisons made.
//******************************************************************************
int LinearSearch(const int ARRAY_SIZE, int targetValue, int array[], 
                 int &linearCounter) {
                 	
//Search for targetValue in array
 for(int i = 0; i < ARRAY_SIZE; i++) {
	linearCounter++;       //Increment counter
	if(array[i] == targetValue) {
     return i;
    }

 }
	return -1;
}

//******************************************************************************
//Definition for BinarySearch function:
// This function performs a binary search on the given array and returns the
// index of the targetValue and counts the number of comparisons made.
//******************************************************************************
int BinarySearch(const int ARRAY_SIZE, int targetValue, int array[], 
                 int &binaryCounter) {
	int first = 0;                 //First number in the array
	int last = ARRAY_SIZE - 1;     //Last number in the array
	
	while(first <= last) {
		int middle = (first + last) / 2;       //Find midpoint
		binaryCounter++;                       //Increment counter
		if(array[middle] == targetValue) return middle;  //Return if found
		else if(array[middle] < targetValue) first = middle + 1; //If top half
		else last = middle - 1;                                 //If bottom half
	}
 return -1;
}