CODEWITHSUNDEEP
c++findset
Alexandru Robert
Alexandru Robert

Reputation: 21

Is find() function efficient for sets?

As far as I am concerned, binary search stands for the most efficient way to determine whethere there exists a certain element x in a sorted array. Thus, I was wondering if it is a good idea to make use of the find() or count() functions in order to perform this process of seeking for an element or it is more reasonable to use a sorted array rather than a set and apply the binary search method.

Upvotes: 2

Views: 106

Answers (2)

Sid S
Sid S

Reputation: 6125

set::find() is fairly efficient, O(log n).

If you don't need to access the elements in order, you should consider using an unordered_set. unordered_set::find() is O(1) on average.

Upvotes: 0

Attersson
Attersson

Reputation: 4876

Yes it is efficient.

A set contains unique and sorted elements. Therefore find() uses binary search and has a O(logN) complexity in a set of N elements. Insertion is logarithmic too, in order to keep it sorted and unique.

Upvotes: 3

Related Questions