Improved intersection of specific sorted sequences

I need perform intersection of 2 ordered sequences [begin1, end1), [begin2, end2). Obvious decision to use std::set_intersection not looks an good idea after review section Possible implementation The matter I don't like this one is in my sequences that is rather big (up to 1e6 items) and I have no clue which one. Following line of code:

while (first1 != last1 && first2 != last2) { ...

means that intersection may run over entire sequence. So my question:

Is there in STL optimized version that may leverage idea of std::lower_bound that can reduce full scan to the O(ln N)