// Program: binary_search_template.cpp
// Author: ...

#include <cassert>
#include <vector>

typedef  std::vector<int>      Vec;
typedef  Vec::const_iterator   cIt;

// PRE: [begin, end) is a valid range whose elements are sorted in
//      non-decreasing order.
// POST: returns a const-iterator to an occurrence of val in [begin, end)
//       or returns end if there is no occurrence
cIt binary_search (cIt begin, cIt end, const int val) {
    // ...
    
}

int main () {
    
    // Test Vectors
    Vec test1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    Vec test2 = {-8, -8, -8, 15, 15, 28, 28};
    Vec test3 (0);
    
    // Execute Some Tests
    assert(binary_search(test1.begin(), test1.end(),    2) == test1.begin()+1);
    assert(binary_search(test1.begin(), test1.end(),    7) == test1.begin()+6);
    assert(binary_search(test2.begin(), test2.end()-3, 28) == test2.end()-3  );
    assert(binary_search(test2.begin(), test2.end(),    7) == test2.end()    );
    assert(binary_search(test3.begin(), test3.end(),    1) == test3.begin()  );
    assert(*binary_search(test2.begin(), test2.end(), -8) == -8 );
    
    return 0;
}