//Cameron Pham             CS1A                       Chapter 8, p. 488, #8
//
/******************************************************************************
* SEARCH FOR BENCHMARKS
* ______________________________________________________________________________
* This program demonstrates and compares two sorting methods. It uses two 
* identical arrays of eight integers, displays the contents of each array, and 
* sorts them. After each pass of both sorting algorithms, the program displays 
* the updated array.
* ______________________________________________________________________________
* INPUT
* Number		// Number that is being searched for
* 
* OUTPUT
* Linear		// Amount of linear search comparisons
* Binary		// Amount of binary search comparisons
*******************************************************************************/
#include <iostream>
using namespace std;
// Function prototypes
int linearSearch(const int [], int, int, int &);
int binarySearch(const int [], int, int, int &);
int main()
{
    // Initialize Variables
    const int SIZE = 20;
    int numbers[SIZE] =
    {
        10, 15, 20, 25, 30, 35, 40, 45, 50, 55,
        60, 65, 70, 75, 80, 85, 90, 95, 100, 105
    };
    int searchValue;           // Value to search for
    int linearComparisons = 0; // Number of linear search comparisons
    int binaryComparisons = 0; // Number of binary search comparisons
    int linearResult;          // Result of linear search
    int binaryResult;          // Result of binary search
    // Ask the user for a value to search for
    cout << "Enter an integer to search for: ";
    cin >> searchValue;
    // Call the linear search function
    linearResult = linearSearch(numbers, SIZE, searchValue,
                                linearComparisons);
    // Call the binary search function
    binaryResult = binarySearch(numbers, SIZE, searchValue,
                                binaryComparisons);
    // Display the search results
    cout << "\nSearch Results" << endl;
    cout << "------------------------------" << endl;
    if (linearResult != -1)
    {
        cout << "Value found: " << searchValue << endl;
        cout << "Linear search comparisons: "
             << linearComparisons << endl;
        cout << "Binary search comparisons: "
             << binaryComparisons << endl;
    }
    else
    {
        cout << "Value was not found in the array." << endl;
        cout << "Linear search comparisons: "
             << linearComparisons << endl;
        cout << "Binary search comparisons: "
             << binaryComparisons << endl;
    }
    return 0;
}
// Function to perform a linear search
int linearSearch(const int array[], int size, int value,
                 int &comparisons)
{
    for (int count = 0; count < size; count++)
    {
        comparisons++;
        if (array[count] == value)
        {
            return count;
        }
    }
    return -1;
}
// Function to perform a binary search
int binarySearch(const int array[], int size, int value,
                 int &comparisons)
{
    int first = 0;
    int last = size - 1;
    int middle;
    while (first <= last)
    {
        middle = (first + last) / 2;
        comparisons++;
        if (array[middle] == value)
        {
            return middle;
        }
        else if (array[middle] > value)
        {
            last = middle - 1;
        }
        else
        {
            first = middle + 1;
        }
    }
    return -1;
}