CODEWITHSUNDEEP
c++11vectortimestlc++14
dynamo
dynamo

Reputation: 126

Time complexity of find fun

Can you explain how find function works in STL C++ vector and what is its time complexity?

vector<int> v;

if(find(v.begin(),v.end(),element)==v.end())
do this;
else 
do this

Upvotes: 1

Views: 11012

Answers (2)

Caleth
Caleth

Reputation: 63297

From [alg.find]

Returns: The first iterator i in the range [first, last) for which the following condition hold: *i == value. Returns last if no such iterator is found.

Complexity: At most last - first applications of the corresponding predicate.

What that means is it will do a linear scan forward, until an value that compares equal to your element is reached.

Upvotes: 3

Adrian W
Adrian W

Reputation: 5036

Have a look at https://en.cppreference.com/w/cpp/algorithm/find

In section "Possible implementation" you can figure out how it works. Details depend on the concrete implementation, which can be different. In any case std::find() will to have to iterate sequentially through your collection and that determines the time complexity. I.e. O(n).

Upvotes: 8

Related Questions