CODEWITHSUNDEEP
binary-searchstd
user4347777
user4347777

Reputation:

Lower_bound vs binary search

I was learning some STL functions and I came across this function lower_bound .I am in a confusion that why doesn't people use lower_bound instead of binary search as both do the same thing ,both of them have O(log n) complexity.

Isn't it better to write just one line code with lower_bound than 8-9 lines of if-else statements with binary search or is their any limitation of lower_bound that I didn't know about because of which people don't use it often?

Upvotes: 5

Views: 3323

Answers (1)

StilesCrisis
StilesCrisis

Reputation: 16290

binary_search is (IMO) poorly named. It tells you via a binary search whether an item exists in your collection. It does not tell you where.

lower_bound tells you where the item should go in the collection, but does not actually verify that the item exists at that place in the collection. You need to check yourself (and be careful not to dereference the end iterator!).

equal_range tells you where the item should go, and (based on the distance between first and second) how many of the item actually exist in the range, or zero if the item doesn't exist. In my opinion it's the most useful. It's slightly slower than lower_bound but not by much.

Upvotes: 10

Related Questions