// Marvyn Jesse De La Torre     CS1A     Chapter 8 #8 pg.488
//
/*************************************************************
* Search Benchmarks
*
* This program compares linear search and binary search
* by counting the number of comparisons required.
*
* Input:
*   num: The number to search for
*
* Output:
*   Displays the comparison count for each search method.
*************************************************************/

#include <iostream>
using namespace std;

int linearSearch(int arr[], int size, int num, int &count);
int binarySearch(int arr[], int size, int num, int &count);

int main()
{
    int arr[] = {
        3, 6, 9, 12, 15, 18, 21, 24, 27, 30,
        33, 36, 39, 42, 45, 48, 51, 54, 57, 60
    };

    int size = sizeof(arr) / sizeof(arr[0]);
    int num;
    int linearCount = 0;
    int binaryCount = 0;

    cout << "Enter the number to search for: ";
    cin >> num;

    int linearResult = linearSearch(arr, size, num, linearCount);
    int binaryResult = binarySearch(arr, size, num, binaryCount);

    if (linearResult == -1)
    {
        cout << "Number was not found using linear search." << endl;
    }
    else
    {
        cout << "Linear search found the number." << endl;
    }

    cout << "Linear search comparisons: " << linearCount << endl;

    if (binaryResult == -1)
    {
        cout << "Number was not found using binary search." << endl;
    }
    else
    {
        cout << "Binary search found the number." << endl;
    }

    cout << "Binary search comparisons: " << binaryCount << endl;

    return 0;
}

int linearSearch(int arr[], int size, int num, int &count)
{
    int position = -1;

    for (int index = 0; index < size && position == -1; index++)
    {
        count++;

        if (arr[index] == num)
        {
            position = index;
        }
    }

    return position;
}

int binarySearch(int arr[], int size, int num, int &count)
{
    int first = 0;
    int last = size - 1;
    int position = -1;

    while (position == -1 && first <= last)
    {
        int middle = (first + last) / 2;

        count++;

        if (arr[middle] == num)
        {
            position = middle;
        }
        else if (arr[middle] > num)
        {
            last = middle - 1;
        }
        else
        {
            first = middle + 1;
        }
    }

    return position;
}