Get iterator to a element in sorted vector in log(n) time.

Question

I have a sorted vector and want to find a particular element in it. I can use binary_search for this but it only tells if it is present or not. I also need an iterator to access the element. Is there an easy way to this or I have to search it sequentially.

Any help appreciated.

Can't you have 3 iterators - one each for beginning, end, and mid? — Rohit Jain, Jul 09 '13 at 16:04
possible duplicate of [Where can I get a "useful" C++ binary search algorithm?](http://stackoverflow.com/questions/446296/where-can-i-get-a-useful-c-binary-search-algorithm) — aaronman, Jul 09 '13 at 16:11

score 7 · Accepted Answer · answered Jul 09 '13 at 16:15

7

Look into lower_bound and upper_bound. lower_bound gives the iterator to the first matching element while upper_bound gives the iterator one past the last matching element.

If either algorithm fails to find a match, it returns an iterator to the place where the item could be inserted to maintain a sorted container.

I've always felt binary_search was misleadingly named.

answered Jul 09 '13 at 16:15

Mark Ransom

299,747
42
398
622

2

Or `equal_range`, which gives you an easy test for present (`first!=second`) and if so gets you the element `*first`. – Yakk - Adam Nevraumont Jul 09 '13 at 16:19
@mark romsom: Yes, and I always felt its wierd there is no "bool contains(start, stop, value)" – Viktor Sehr Jul 09 '13 at 17:36

score 1 · Answer 2 · edited May 23 '17 at 10:32

1

std::lower_bound will return the first element that is not less than your value. Meaning if the element returned is equal to your value your good, if it is not equal or the end iterator than the right element hasn't been found.

Here is the code from the dupe

template<class Iter, class T>
Iter binary_find(Iter begin, Iter end, T val)
{
    // Finds the lower bound in at most log(last - first) + 1 comparisons
    Iter i = std::lower_bound(begin, end, val);

    if (i != end && !(val < *i))
        return i; // found
    else
        return end; // not found
}

Remember if you use std::upper_bound than it returns the first greater element so it is not as easy to adapt to your purposes because if your element is indeed found you have to decrement the iterator and even then you still may not find it

edited May 23 '17 at 10:32

Community

1
1

answered Jul 09 '13 at 16:23

aaronman

18,343
7
63
78

2

And as I commented in the dupe: Don't use `*i == val`! Rather use `!(val < *i)`. The reason is that `lower_bound` uses `<`, not `==` (i.e. `T` is not even required to be equality-comparable). (See Scott Meyers' _Effective STL_ for an explanation of the difference between _equality_ and _equivalence_.) – gx_ Jul 09 '13 at 16:30
@gx_ Thank you for the advice, I marked the question as a dupe and only posted the answer because the other answer was insufficient – aaronman Jul 09 '13 at 16:32
2

Well, for completeness: after `i = std::lower_bound(begin, end, val)` there are only 2 possibilities (by specification): either (1) `i == end`, or (2) (`i != end` and) `!(*i < val)`. In case (2), we must still add the "swapped" test: if `!(*i < val) && !(val < *i)` (i.e. `!(*i < val || val < *i)`) then `*i` and `val` are equivalent (neither is less than the other). – gx_ Jul 09 '13 at 16:46
@gx_ thank you for fixing the errors I wonder why the answer I took it from never bothered to fix it – aaronman Jul 09 '13 at 21:14
No no no your last edit is wrong, the code `if (i != end && !(val < *i))` was correct! We must _first_ test if `i != end`, and if so _then_ `*i` is a valid expression and we _already know_ from the specification of `lower_bound` that `!(*i < val)` is true, so the only test that remains to be done explicitly is the "swapped" `!(val < *i)` (sorry if my second comment was confusing :s). (As for the source answer not "fixed": maybe because it's years old and I just commented :)) – gx_ Jul 10 '13 at 08:08

Get iterator to a element in sorted vector in log(n) time.

2 Answers2