// binsearch4.cpp
// Glenn G. Chappell
// 30 Sep 2009
//
// For CS 311 Fall 2009
// Binary Search
// Version #4: Iterative (tail recursion eliminated)

#include <iostream>
using std::cout;
using std::endl;
using std::cin;
#include <cstdlib>
using std::size_t;
#include <algorithm>
using std::distance;
using std::advance;


// binSearch
// Does Binary Search on a range specified with iterators.
// Requirements on types:
//     FDIter is a forward iterator type.
//     ValueType is the value type of FDIter.
//     operator< is a total order on ValueType.
// Pre:
//     [first, last) is a valid range.
//     Values in the range are sorted by < (ascending).
// Post:
//     Return is true if findMe was found (using equivalence) in range,
//      false otherwise.
// If ValueType operator< throws, then binSearch throws the same exception.
// Otherwise, will not throw.
template <typename FDIter, typename ValueType>
bool binSearch(FDIter first,      // Iterator to first item in range
               FDIter last,       // Iterator to one-past last item in range
               const ValueType & findMe)  // value to find
{
    while (true)  // For tail-recursion elimination
    {
        size_t size = distance(first, last);

        // BASE CASE of former recursive function

        if (size <= 1)
        {
            if (size == 0)
                return false;
            return !(*first < findMe) && !(findMe < *first);
        }

        // RECURSIVE CASE of former recursive function

        // Get iterator to middle position of range
        FDIter pivotIter = first;
        advance(pivotIter, size/2);

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

        // Tail-recursive call is gone, replaced by loop
        // return binSearch(first, 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;
    cout << endl;

    cout << "Press ENTER to quit ";
    while (cin.get() != '\n') ;

    return 0;
}