// This code is in C++11

#include <iostream>
#include <algorithm>
#include <functional>
#include <memory>
#include <climits>
#include <iterator>

using namespace std;

// :), generic functor
template <typename ArgType, typename ResultType>
struct PredUniqueElements : public std::unary_function<ArgType, ResultType> {

public:
    PredUniqueElements(ArgType ref) : prev(ref) {}
    
   ResultType operator() (ArgType curr) {
      ArgType old = prev;
      prev = curr;
      return curr != old;
   }

private:
    ArgType prev;
};

int GenerateDataSet(int A[], int size) {
    for(int i = 0; i < size; i++)
        A[i] = rand()%size;

    sort(A, A+size);
    
    // predicate funtor definition
    PredUniqueElements<int, bool> pred(INT_MIN);

    // Retain only unique elements
    auto it = copy_if (A, A+size, A, pred);
    return distance(A, it);
}

// Returns location of key, or -1 if not found
int BinarySearchSimple(int A[], int l, int r, int key, int &count)
{
    int m;
 
    while( l <= r )
    {
        m = l + (r-l)/2;
 
        count++;
        if( A[m] == key ) // first comparison
            return m;
 
        count++;
        if( A[m] < key ) // second comparison
            l = m + 1;
        else
            r = m - 1;
    }
 
    return -1;
}

int BinarySearch(int A[], int l, int r, int key, int &count)
{
    int m;
 
    while( r - l > 1 )
    {
        m = l + (r-l)/2;
 
        count++;
        if( A[m] <= key )
            l = m;
        else
            r = m;
    }
 
    count++;
    if( A[l] == key )
        return l;
    else
        return -1;
}

void TestCase_01() {
    int size = 2048;
    auto_ptr<int> buf(new int[size]);
    int *A = buf.get();
    
    size = GenerateDataSet(A, size);
    
    copy(A, A+size, ostream_iterator<int>(cout, " ")), cout << endl;
    
    int key = 193;
    int count;
    
    // We are only interested in comparison count
    count = 0;
    BinarySearchSimple(A, 0, size-1, key, count);
    cout << "BinarySearchSimple " << count << endl;
    
    count = 0;
    BinarySearch(A, 0, size-1, key, count);
    cout << "BinarySearch " << count << endl;
}

int main() {
    srand(unsigned(time(NULL)));
    
    TestCase_01();
    
    return 0;
}