//Ryan Shahriyarpour   CS1A  Chapter 8   Question 8
/*****************************************************************************
 * 
 * Search Benchmarks
 * 
 *********************
 * 
 * This program stores 20 sorted integers in an array and lets the user
 * pick a value to look for. The value is located twice, once with a linear
 * search and once with a binary search. Each search counts how many
 * comparisons it makes so the two methods can be compared.
 * 
 * *******************
 * One comparison is counted each time an array element is checked against
 * the value being searched for.
 *  Linear search - checks the elements one at a time from the start.
 *  Binary search - checks the middle of the remaining range each time.
 *                  (The array has to be sorted, and this one is.)
 * 
 * INPUT
 *  searchValue  - the integer to search for
 * 
 * OUTPUT    
 *  The number of comparisons used by the linear search
 *  The number of comparisons used by the binary search
 * 
 ****************************************************************************/
 
#include <iostream>
using namespace std;
 
// Constant for the number of array elements
const int SIZE = 20;
 
// Function prototypes (each returns the index found, or -1 if not found)
int linearSearch(const int array[], int size, int value, int &comparisons);
int binarySearch(const int array[], int size, int value, int &comparisons);
 
int main()
{
    // data dictionary
    int numbers[SIZE] = {           // Sorted array of integers
         3,  7, 12, 18, 24, 29, 35, 41, 46, 52,
        58, 63, 69, 74, 80, 86, 91, 95, 98, 103
    };
    int searchValue;                // Value the user wants to find
    int position;                   // Index returned by a search
    int linearCount = 0;            // Comparisons made by the linear search
    int binaryCount = 0;            // Comparisons made by the binary search
 
    // Get the value to search for
    cout << "Array: 3 7 12 18 24 29 35 41 46 52 "
         << "58 63 69 74 80 86 91 95 98 103" << endl;
    cout << "Enter a value to search for: ";
    cin >> searchValue;
 
    // Run both searches
    position = linearSearch(numbers, SIZE, searchValue, linearCount);
    binarySearch(numbers, SIZE, searchValue, binaryCount);
 
    // Display the results
    if (position == -1)
        cout << "\n" << searchValue << " was not found in the array." << endl;
    else
        cout << "\n" << searchValue << " was found at index "
             << position << "." << endl;
 
    cout << "Linear search comparisons: " << linearCount << endl;
    cout << "Binary search comparisons: " << binaryCount << endl;
 
    return 0;
}
 
// Linear search; comparisons goes up by one for each element checked
int linearSearch(const int array[], int size, int value, int &comparisons)
{
    // data dictionary
    int index;                      // Loop counter
    int position = -1;              // Index of the match (-1 = not found)
 
    for (index = 0; index < size; index++)
    {
        comparisons++;
        if (array[index] == value)
        {
            position = index;
            break;
        }
    }
    return position;
}
 
// Binary search; comparisons goes up by one for each middle element checked
int binarySearch(const int array[], int size, int value, int &comparisons)
{
    // data dictionary
    int first = 0;                  // First index still being searched
    int last = size - 1;            // Last index still being searched
    int middle;                     // Middle index of the range
    int position = -1;              // Index of the match (-1 = not found)
    bool found = false;             // True once the value is located
 
    while (!found && first <= last)
    {
        middle = (first + last) / 2;
        comparisons++;
        if (array[middle] == value)
        {
            found = true;
            position = middle;
        }
        else if (array[middle] > value)
            last = middle - 1;
        else
            first = middle + 1;
    }
    return position;
}