#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

int main(void)
{
    function<int(vector<int>&, int)> linear = [&linear](vector<int>& v, int value)
    {
        size_t first = 0, last = v.size() - 1;
        
        while (first <= last)
        {
            size_t mid = first + (last - first)/2;
            
            if (value == v[mid])
                return value;

            if (value > v[mid])
                first = mid + 1;
            
            else // value < v[mid]
                last = mid - 1;

        }

        return -1;
    };

    function<int(vector<int>&, size_t, size_t, int)> recursive = [&recursive](vector<int>& v, size_t first, size_t last, int value)
    {
        if (first <= last)
        {
            size_t mid = first + (last-first)/2;
            
            if (value == v[mid])
                return value;
            
            if (value > v[mid])
                return recursive(v, mid + 1, last, value);
            
            else // value < v[mid])
                return recursive(v, first, mid - 1, value);
        }
        return -1;
    };
    
    string s;

    vector<int> v1{1,2,3,4,6,7,8,9,10}; s = "vec: "; for (auto& i: v1) s += to_string(i) + " ";
    cout << s << " linear search: 3 result: " << linear(v1, 3) << endl;
    cout << s << " linear search: 5 result: " << linear(v1, 5) << endl;

    cout << s << " recursive search: 3 result: " << recursive(v1, 0, v1.size() - 1, 3) << endl;
    cout << s << " recursive search: 5 result: " << recursive(v1, 0, v1.size() - 1, 5) << endl;

    vector<int> v2{1,2,3,4,6,7,8,9,10,11}; s = "vec: "; for (auto& i: v2) s += to_string(i) + " ";
    cout << s << " linear search:  3 result: " << linear(v2, 3) << endl;
    cout << s << " linear search:  5 result: " << linear(v2, 5) << endl;
    cout << s << " linear search:  1 result: " << linear(v2, 1) << endl;
    cout << s << " linear search: 11 result: " << linear(v2, 11) << endl;

    cout << s << " recursive search:  3 result: " << recursive(v2, 0, v2.size() - 1, 3) << endl;
    cout << s << " recursive search:  5 result: " << recursive(v2, 0, v2.size() - 1, 5) << endl;
    cout << s << " recursive search:  1 result: " << recursive(v2, 0, v2.size() - 1, 1) << endl;
    cout << s << " recursive search: 11 result: " << recursive(v2, 0, v1.size() - 1, 11) << endl;
    
    return 0;
}