//
//
//
#include <iostream>
using namespace std;

int linearSearch(int[], int, int, int&);
int binarySearch(int[], int, int, int&);

int main(){

    const int SIZE = 20;
    int array[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
                 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};

    int num,
        binresult,
        linresult,
        value,
        result1 = 0,
        result2 = 0;

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

    linresult = linearSearch( int list[], SIZE, value, result1);
    binresult = binarySearch(array, SIZE, value, result2);


    cout << "Linear search: " << linearSearch << endl;
    cout << "Binary search: " << binarySearch << endl;

    return 0;
}

int linearSearch(int list[], int SIZE, int value, int& result1){

    int index = 0;
    int position = -1;
    bool found = false;

    while (index < SIZE && !found){

        if (list[index] == value){

            found = true;
            position = index;
        }
        index++;

        if (position == -1)
            result1++;
    }
    return position;
}

int binarySearch(int array[], int SIZE, int value, int& result2){

    int first = 0,
        last = SIZE - 1,
        middle,
        position = -1;
    bool found = false;

    while (!found && first <= last){

        middle = (first + last) / 2;
        if (array[middle] == value)
        {
            found = true;
            position = middle;
        }
        else if (array[middle] == value)
            last = middle - 1;
        else
            first = middle + 1;

        if (position == -1)
            result2++;
    }
    return position;
}