// Prog: binary_search_test.cpp
// test your binary search function!

#include <iostream>
#include <cassert>
#include <vector>

typedef std::vector<int>::const_iterator Cvit;

// PRE:  [begin, end) is a valid range, and the elements *p,
//       p in [begin, end) are in ascending order
// POST: return value is an iterator p in [begin, end) such
//       that *p = x, or the iterator end, if no such iterator
//       exists
Cvit bin_search (const Cvit begin, const Cvit end, const int x)
{
  // enter your code here!
  return end;
}

int main() 
{  
  // input length of test array, n >= 0
  int n;
  std::cin >> n;

  std::vector<int> v(n);

  // 0, 2, 4, 6,... 
  for (int i=0; i<n; ++i) v[i] = 2*i;

  // test binary search 
  for (int i=0; i<2*n; i+=2)
    assert (bin_search (v.begin(), v.end(), i) == v.begin()+i/2); 
  for (int i=-1; i<2*n+2; i+=2)
    assert (bin_search (v.begin(), v.end(), i) == v.end());     
  
  // special case: empty range!
  assert( bin_search (v.begin(), v.begin(), 0) == v.begin());
  
  std::cout << "The search function seems to work as expected!\n";
  
  return 0;
}