How do I perform a binary search on a vector to find an element with a specific id?
I have a sorted vector and now I would like to find elements from this vector that have a specific id. std::binary_search
just tells me if the element exists, so I use std::lower_bound
:
#include <vector>
#include <iostream>
#include <algorithm>
struct Foo {
int id;
// ... more members ... //
Foo(int id) : id(id) {}
};
bool compareById(const Foo& a,const Foo& b) { return a.id < b.id; }
int main(){
std::vector<Foo> vect;
vect.push_back(10);
vect.push_back(123);
vect.push_back(0);
std::sort(vect.begin(),vect.end(),compareById);
int id_to_find = 1;
std::vector<Foo>::iterator f = std::lower_bound(vect.begin(),vect.end(),Foo(id_to_find),compareById);
if (f != vect.end() && f->id == id_to_find) { std::cout << "FOUND"; }
}
This kind works, but I strongly dislike what I need to create Foo(id_to_find)
in order to pass it to std::lower_bound
, and then I need to double check if the item I received is the one I was looking for.
I think I could use find_if
to avoid creating this extra instance, but as far as I know, it find_if
is only linear and does not use a sorted vector. I'm a little surprised that I can't find the correct algorithm for the problem, and I'm already considering writing my own.
What's the best way to do this?
source to share
There are several things you can do to make your life easier. First, the comparator doesn't need to have the same parameter for the first and second parameters. The requirement is that the first parameter must be implicitly converted to a dereferenced iterator, and the second parameter must be implicitly converted to the type of the third parameter passed to lower_bound
.
We can use that and just take it int
as the second parameter, so you don't need to create Foo
. This allows us to do compareFooById
both:
bool compareFooById(const Foo& a,const int& b) { return a.id < b; }
And now we can use it now like:
std::vector<Foo>::iterator f = std::lower_bound(vect.begin(), vect.end(), id_to_find, compareFooById);
Note that I've added a new feature here. You are using compareById
for std::sort
, so I couldn't just change it as it would break the call sort
.
Now, when you need to check if you have a valid iterator, you have a couple of options. You can write a wrapper function that references the iterator to fill and return if it found an element. It will look like
template<typename It, typename Value, typename Comp
bool my_binary_search(It begin, It end, Value val, Comp c, It& ret)
{
ret = std::lower_bound(begin, end, val, c);
return ret != end;
}
and then you call it
std::vector<Foo>::iterator f;
if(my_binary_search(vect.begin(), vect.end(), id_to_find, compareFooById, f))
//do something with f.
Another option is to throw an exception if the item is not found. This, in my opinion, is not what you are doing, although if you do not find the element, this is indeed an exceptional case.
source to share