// Timothy Price				CS1A				Ch 8 Challenge 8
/******************************************************************************
 * Compare search algorithms 
 * 
 * Compares the efficiency of linear search and binary search algorithms by 
 * locating a target value within a sorted array of integers and displaying 
 * their performance metrics on the screen.
 * Inputs:
 *  A target integer value to locate 
 *  An array of 20 sorted integers 
 * 
 * Outputs:
 *  The index position where the target value is found (or a not-found status)
 *  The total number of comparisons made by the linear search algorithm
 *  The total number of comparisons made by the binary search algorithm
 *****************************************************************************/

#include <iostream>

using namespace std;

// Function prototypes
int linearSearch(const int arr[], int size, int target, int& comparisons);
int binarySearch(const int arr[], int size, int target, int& comparisons);

int main() {
    // Array of 20 sorted integers
    const int SIZE = 20;
    int numbers[SIZE] = {
        12, 18, 25, 31, 44, 52, 63, 70, 78, 85,
        92, 105, 112, 120, 135, 142, 155, 168, 180, 195
    };

    int target = 12; // The value we want to locate
    int linearComparisons = 0;
    int binaryComparisons = 0;

    cout << "Searching for target value: " << target << endl;
    cout << "----------------------------------------" << endl;

    // Call Linear Search
    int linearIndex = linearSearch(numbers, SIZE, target, linearComparisons);
    if (linearIndex != -1) {
        cout << "Linear Search:" << endl;
        cout << "  - Status: Found at index " << linearIndex << endl;
        cout << "  - Comparisons made: " << linearComparisons << endl << endl;
    } else {
        cout << "Linear Search: Value not found. Comparisons: ";
        cout << linearComparisons << endl << endl;
    }

    // Call Binary Search
    int binaryIndex = binarySearch(numbers, SIZE, target, binaryComparisons);
    if (binaryIndex != -1) {
        cout << "Binary Search:" << endl;
        cout << "  - Status: Found at index " << binaryIndex << endl;
        cout << "  - Comparisons made: " << binaryComparisons << endl << endl;
    } else {
        cout << "Binary Search: Value not found. Comparisons: "; 
        cout << binaryComparisons << endl << endl;
    }

    return 0;
}

// Function that performs a linear search and counts comparisons
int linearSearch(const int arr[], int size, int target, int& comparisons) {
    comparisons = 0;
    for (int i = 0; i < size; ++i) {
        comparisons++; // Increment comparison counter for each check
        if (arr[i] == target) {
            return i; // Index where the value was found
        }
    }
    return -1; // Value not found
}

// Function that performs a binary search and counts comparisons
int binarySearch(const int arr[], int size, int target, int& comparisons) {
    comparisons = 0;
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        comparisons++; // Count the equality check (arr[mid] == target)
        if (arr[mid] == target) {
            return mid; // Index where the value was found
        }

        comparisons++; // Count the relational check (arr[mid] < target)
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1; // Value not found
}