hellomoto's blog

upper_bound
By hellomoto, history, 7 years ago, In English

How internally upper_bound for sorted vector(in ascending order) works in c++. Let say 'A' is a sorted vector.Then how upper_bound(A.begin(),A.end(),x) will directly give iterator to first element greater than x. Thanks in advance.

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hellomoto (previous revision, new revision, compare).

→ Reply
»
7 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

The functional behavior of the std::upper_bound() template is described in www.cplusplus.com.

It is basically based on binary search. Therefore, its time-complexity should be , provided that random-access of any item is done in constant-time that is independent of problem size which is the count of items between the first and the last item.

→ Reply