Difference Between std::lower_bound(set.begin(), set.end(), val) and set.lower_bound(val)?

Revision en1, by mtr361, 2019-01-15 02:25:21

On CF 256 Problem A, I use lower_bound to binary search. However, I've found that using std::lower_bound(set.begin(), set.end(), val) makes the solution blow up, resulting in TLE (>3000ms), while using set.lower_bound(val) works perfectly fine (~300ms).

AC (358ms): 48402685 TLE (3000ms): 48402684

It appears, then, that std::lower_bound(set.begin(), set.end(), val) is not actually binary searching. What is causing this behavior?

Thank you!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English mtr361 2019-01-15 02:26:29 19 Tiny change: 'ary search. However,' -> 'ary search on a std::set<int>. However,'
en1 English mtr361 2019-01-15 02:25:21 616 Initial revision (published)