Sign in to follow this  
hiigara

[STL] How do I perform Binary Search on a STL or regular Vector?

Recommended Posts

Quote:
Original post by SiCrane
Generally by using one of the functions std::binary_search()
std::binary_search() only checks for existence, it won't tell you where or what it is.

Quote:
std::lower_bound() or std::upper_bound()

... and std::equal_range(), which lets you find all of them that match.

Share this post


Link to post
Share on other sites
As an aside, if you need sorting and searching you are probably better off with one the associative containers: map, multimap, set, and multiset.

The containers are automatically sorted and the member functions automatically use binary searches.

Share this post


Link to post
Share on other sites
Quote:
Original post by frob
As an aside, if you need sorting and searching you are probably better off with one the associative containers: map, multimap, set, and multiset.

The containers are automatically sorted and the member functions automatically use binary searches.
Not if your program sets up the container at startup and then simply performs just lookups for the most part of your program. In such a case using a sorted vector and equal_range will perform much better in all respects.

Share this post


Link to post
Share on other sites
Quote:
Original post by iMalc
Quote:
Original post by frob
As an aside, if you need sorting and searching you are probably better off with one the associative containers: map, multimap, set, and multiset.

The containers are automatically sorted and the member functions automatically use binary searches.
Not if your program sets up the container at startup and then simply performs just lookups for the most part of your program. In such a case using a sorted vector and equal_range will perform much better in all respects.

Yes, there are many design decisions like that.

If you have scenario A then you should use option X.
If you have scenario B then you should use option Y.
If you have scenario C then you should use option Z.

You scenario -- a single sort one time with no subsequent modifications, performing particular searches, is just one particular usage pattern.


I was simply bringing up that other containers are designed for sorting and searching.

Share this post


Link to post
Share on other sites
Thanks. My Scenario is: I calculate a Table of Stopping Distances for each Speed once. Speed 10 would have Stopping Distance:
Stoppingdistance[10]
Then during the Simulation I search for the Target Distance in the Stoppingdistance Array to know what Speed to proceed. Obviously the Stopping Distance increases with Speed, so the Table is automatically ordered.
upper_bound() is what I need.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this