Robert Gould - 2 months ago 9x

C++ Question

I need a binary search algorithm that is compatible with the C++ STL containers, something like

`std::binary_search`

`<algorithm>`

(On a side note, what the hell was the standard committee thinking when they defined the API for binary_search?!)

so far

`lower_bound`

`upper_bound`

`//lousy pseudo code`

vector(1,2,3,4,6,7,8,9,0) //notice no 5

iter = lower_bound_or_upper_bound(start,end,5)

iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6

`lower_bound`

`upper_bound`

`boost::binary_search`

Answer

There is no such functions, but you can write a simple one using `std::lower_bound`

, `std::upper_bound`

or `std::equal_range`

.

A simple implementation could be

```
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
}
```

Another solution would be to use a `std::set`

, which guarantees the ordering of the elements and provides a method `iterator find(T key)`

that returns an iterator to the given item. However, your requirements might not be compatible with the use of a set (for example if you need to store the same element multiple times).

Source (Stackoverflow)

Comments