CODEWITHSUNDEEP
c++algorithmstd
user123 456
user123 456

Reputation: 35

std:find() for sorted vs unsorted

Consider two integer vectors v1 and v2, where v1 is sorted and v2 is not sorted. What would be the time complexities to search for an element in these two vectors using find()?

Upvotes: 1

Views: 1910

Answers (2)

Martin Perry
Martin Perry

Reputation: 9527

The time complexity of std::find will always be linear O(n), because it has no knowledge of the std::vector. It must consider vector as non-sorted and perform linear search over all elements.

However, real-time may depend on circumstances. Sorting may help because std::find can end up sooner. It depends on what you are looking for. Let's say you are looking for 2 in a non-sorted array (5,1,3,4,2) - you have to compare all elements. But for sorted (1,2,3,4,5) - you compare only two elements and find the 2.

Upvotes: 3

jfMR
jfMR

Reputation: 24788

std::find() performs linear search, i.e., it goes element by element until it finds the value it's looking for. It is linear regardless of whether or not the collection is sorted.

If you have a sorted vector, you may want to consider performing binary search with std::lower_bound() instead. This will be logarithmic in the size of the vector.

Upvotes: 10

Related Questions