//! \brief A recursive binary search using STL vectors
//! \param vec The vector whose elements are to be searched
//! \param start The index of the first element in the vector
//! \param end The index of the last element in the vector
//! \param key The value being searched for
//! \return The index into the vector where the value is located,
//! or -1 if the value could not be found.
template<typename T>
int binary_search(const std::vector<T>& vec, int start, int end, const T& key)
{
    // Termination condition: start index greater than end index
    if(start > end)
    {
        return -1;
    }

    // Find the middle element of the vector and use that for splitting
    // the array into two pieces.
    const int middle = start + ((end - start) / 2);

    if(vec[middle] == key)
    {
        return middle;
    }
    else if(vec[middle] > key)
    {
        return binary_search(vec, start, middle - 1, key);
    }

    return binary_search(vec, middle + 1, end, key);
}

#include <vector>
#include <cassert>
using namespace std;

//! \brief A helper function for the binary search
template<typename T>
int search(const vector<T>& vec, const T& key)
{
    return binary_search(vec, 0, vec.size()-1, key);
}

int main()
{
    // Create and output the unsorted vector
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(5);
    vec.push_back(13);
    vec.push_back(18);
    vec.push_back(21);
    vec.push_back(43);
    vec.push_back(92);

    // Use our binary search algorithm to find an element
    int search_vals[] = {1, 5, 19, 21, 92, 43, 103};
    int expected_vals[] = {0, 1, -1, 4, 6, 5, -1};

    for(unsigned i = 0; i < 7; i++)
    {
        assert(expected_vals[i] == search(vec, search_vals[i]));
    }

    return 0;
}

//! \brief A more generic binary search using C++ templates and iterators
//! \param begin Iterator pointing to the first element
//! \param end Iterator pointing to one past the last element
//! \param key The value to be searched for
//! \return An iterator pointing to the location of the value in the given
//! vector, or one past the end if the value was not found.
template<typename Iterator, typename T>
Iterator binary_search(Iterator& begin, Iterator& end, const T& key)
{
    // Keep halving the search space until we reach the end of the vector
    const Iterator NotFound = end;

    while(begin < end)
    {
        // Find the median value between the iterators
        const Iterator Middle = begin + (std::distance(begin, end) / 2);

        // Re-adjust the iterators based on the median value
        if(*Middle == key)
        {
            return Middle;
        }
        else if(*Middle > key)
        {
            end = Middle;
        }
        else
        {
            begin = Middle + 1;
        }
    }

    return NotFound;
}

//! \A common binary search Algorithm with its pseudocode

    bool binarySearch(int array[], int Size, int key, int& location)
    {
	int low = 0, high = Size - 1, midpoint = 0;
	while (low <= high)
	{
		midpoint = low + (high - low)/2;
		if (key== array[midpoint])
		{
			location = midpoint;
			return true;
		}
		else if (key< array[midpoint])
			high = midpoint - 1;
		else
			low = midpoint + 1; //when key is > array[midpoint]
	}
	return false;
    }