#include <algorithm>
#include <functional>
#include <vector>

template<class T>
std::vector<T>::iterator
seq_search (const T& el,
	    std::vector<T>::iterator begin,
	    std::vector<T>::iterator end)
{
  for (std::vector<T>::iterator i = begin; i != end; ++i)
    {
      std::cout << "el: " << *i << std::endl;
      if (el == *i) {
	std::cout << "Found something" << std::endl;
	return i;
      }
    }
  return std::vector<T>::iterator ();
}

template<class T>
std::vector<T>::iterator
bin_search (const T& el,
	    std::vector<T>::iterator begin,
	    std::vector<T>::iterator end)
{
  std::vector<T>::iterator middle;
  end -= 1;
  while (begin <= end)
    {
      middle = begin + ((end - begin) / 2);
      std::cout << "Index: " << *middle << std::endl;
      if (el == *middle)
	return middle;
      else if (el < *middle)
	{
	  end = middle - 1;
	}
      else if (el > *middle)
	{
	  begin = middle + 1;
	}
    }

  return std::vector<T>::iterator ();
}

int main ()
{
  std::vector<int> seq;

  srand (time (NULL));
  seq.resize (100000);
  for (int i = 0; i < 100000; ++i)
    {
      seq[i] = rand ();
    }
  sort(seq.begin (), seq.end ());
  
  std::vector<int>::iterator i = bin_search (rand (), seq.begin (), seq.end ());

  if (i != std::vector<int>::iterator ())
    {
      std::cout << "Found: " << *i << std::endl;
    }
  else 
    {
      std::cout << "Found nothing" << std::endl;
    }

  return 0; 
}

// EOF //