Re: binary_search

[Paavo Helde]

On 19.11.2016 23:57, Stefan Ram wrote:
> Why does ::std::binary_search return a boolean?
> Why doesn't it return an iterator to the position
> found? Wouldn't more information sometimes be
> helpful to the caller?

std::lower_bound, std::upper_bound

[Ike Naar]

On 2016-11-19, Stefan Ram <r...@zedat.fu-berlin.de> wrote:
> Why does ::std::binary_search return a boolean?
> Why doesn't it return an iterator to the position
> found?

There can be more than one position that contains the value being
searched for.

[Juha Nieminen]

Note, however, that those functions don't actually tell if a value equal
to the parameter exists within the range. Instead, they give an iterator
which points to the location where you would have to insert the searched
value in order to keep the range sorted.

(Their difference is that if there exist values within the range that
are equal to the one given as parameter, the lower_bound will return
the first position where it can be inserted, while upper_bound returns
the last position. In either case the range would remain sorted if you
insert the value in that position. The location may just be different.)

Which means in practice that even if there is no value equal to the one
given as parameter within the range, they will still return an iterator
that points within the range (or to the end if the value in question would
need to be inserted there for the range to remain sorted).

With std::lower_bound() you need to make an additional equality check
to see if the value pointed by the returned iterator is equal to the
searched value.