I have a set as

set<int> s;

I used lower_bound(s.begin(),s.end(),x)

It gave me TLE.

Then i used s.lower_bound(x)

My solution passed.

Whats the difference in both? I mean why is it happening?

First one is working in O(n) time while latter in O(logn).

Weren't both supposed to be O(logn) ?

Auto comment: topic has been updated by root8950 (previous revision, new revision, compare).STL was designed to be universal and flexible.

There are a bunch of containers, and all of them need to support universal operations like iterating through elements, sorting, finding element, etc. So instead of implementation multiple methods

`container.sort()`

in all of the containers, which for majority of them will be the same algorithm, STL offers one unified function`std::sort()`

, which can be used to sort different containers. Same with function`std::lower_bound()`

.However, due to internal model of containers not all of them use the same algorithm. For example, you cannot access elements in random order in

`list`

like you do in vector. So for that case, there are methods designed specifically for the container. So list have method`list::sort()`

which use algorithm specific for linked list structure.Just same story with

`set`

and`lower_bound()`

. There is a unified function`std::lower_bound()`

, which works in O(logN) on Random Access Iterators, and O(N) on other iterators. Container`std::set`

has Bidirectional Iterator and cannot provide random access to its members. So unified`std::lower_bound()`

works in O(N). Yet, container`set`

is binary search tree and can find lower bound in O(logN) usingdifferentalgorithm,specificfor internal structure of`std::set`

. It is implemented in method`set::lower_bound()`

, which works in O(logN).This is one of the fundamental ideas in STL, so I recommend you to read some literature about STL in general.

Hope that helps, feel free to ask/correct something.

Is there a stl for finding just immediate lower or equal value than key in map/set In lower_bound I get iterator to the key or next immediategreater value Is there any stl for getting iterator to the key or immediate smaller value than key

One way is to simply use

`set<int, greater<int>>`

, then`lower_bound`

does what you ask for.If you need to have both immediate greater and immediate smaller, then do the following. Suppose you want the immediate strictly lower value of

`x`

in the set`s`

. If`s.lower_bound(x) == s.begin()`

, there is no answer; otherwise the iterator is`prev(s.lower_bound(x))`

.By the way I think it would be better to make a new blog instead of commenting on a mostly-irrelevant old blog.

I feared of getting no reply or may be I asked a stupid question...Many times I feel like to make a new post. But eventually can't for some psychological issue. In future I would try to do like you advised. Thank you