This draft is 4 years old, so its time to post it, especially, since I found a bug in the code.

I just returned to violet and decided it is time to increase my contribution before next div 1 contest makes me blue again. had bad luck to learn binary search from informatics.mccme.ru (I think they rewrote article from that time but the irreversible damage was done and even after explaining tricks by my friends AndrewB330 and nagibator I still can not write binary search without bugs). And I was searching for easy tricks to use lower and upper bound functions of the STL library (yes I am talking about C++ only) to solve binary search problems. Anyway, you usually need to find the first element satisfying or not satisfying some conditions. So you can easily implement your "Iterator" class with difference, prefix increment, increment, not equal operator and dereference operator:

struct BinarySearchIterator : public iterator<random_access_iterator_tag, bool>
{
  long long value;

  typename iterator_traits<BinarySearchIterator>::difference_type operator - (const BinarySearchIterator &it) const { return value - it.value; }

  BinarySearchIterator& operator ++() { return *this += 1; }

  BinarySearchIterator& operator --() { return *this += -1; } // msys

  BinarySearchIterator& operator +=(typename iterator_traits<BinarySearchIterator>::difference_type n) { value += n; return *this;}

  bool operator != (const BinarySearchIterator &it) const { return value != it.value; }

  bool operator*() const {
    /* code here */
    return true;
  }
};

Since I wrote this post, Python has entered our lives. And those who use it for CP probably aware that one of the rare things from STL which exists in Python is the bisect module with bisect_left (equivalent to lower_bound) and bisect_right (equivalent to upper_bound). So we can abuse it to do binary search as well:

class BinarySearchCollection(object):
    def __init__(self, length=None):
        self.__length = length

    def __len__(self):
        return self.__length

    def __getitem__(self, item):
        raise NotImplementedError()

List of problems:

• 1251D - Salary Changing

• Blindfolded Bullseye

• New Elements: Part 2

Enjoy.