// binsearch1.cpp
// Glenn G. Chappell
// 18 Feb 2008
//
// For CS 311 Spring 2008
// Binary Search
// Version #1: Recursive


#include <iostream>
using std::cout;
using std::endl;


// binSearch
// Does Binary Search on a range specified with iterators.
// Recursive.
// Requirements on types:
//     RAIter is a random-access iterator type.
//     ValueType is the value type of RAIter.
//     ValueType is copy-constructable.
//     ValueType has a public dctor.
//     operator< is a total order on ValueType.
//     ValueType is equality comparable (with operator==).
// Pre:
//     [first, last) is a valid range.
//     Values in the range are sorted by < (ascending).
// Post:
//     Return is true if findMe was found (using equality) in range,
//      false otherwise.
// If ValueType copy ctor, operator<, operator==,
//  or dctor throws, then binSearch throws the same exception.
// Otherwise, will not throw.
template <typename RAIter, typename ValueType>
bool binSearch(RAIter first,      // Iterator to first item in range
               RAIter last,       // Iterator to one-past last item in range
               ValueType findMe)  // value to find
{
    // BASE CASE

    if (last == first+1)
    {
        return *first == findMe;
    }
    if (last == first)
    {
        return false;
    }

    // RECURSIVE CASE

    // Get iterator to middle position of range
    RAIter pivotIter = first + (last - first)/2;

    if (findMe < *pivotIter)
    {   // Recursively search first half of range
        return binSearch(first, pivotIter, findMe);
    }
    else
    {   // Recursively search second half of range
        return binSearch(pivotIter, last, findMe);
    }
}


// Main program
// Demonstrates use of function binSearch
int main()
{
    // Set up array
    const int SIZE = 100000;
    int arr[SIZE];
    for (int i = 0; i < SIZE; ++i)
        arr[i] = 10*i;

    int value = 40;  // Value to search for

    // Do a search
    bool success = binSearch(arr, arr + SIZE, value);

    // Print result
    if (success)
        cout << value << " FOUND" << endl;
    else
        cout << value << " not found" << endl;
}