Observe that you can restrict your code to only call std::advance on the iterator. So definitely you could do binary search without random access, and you would actually iterate over all elements, but you just skip the comparison function for the majority of elements.
