std::binary_search(), iterator to the found element and timecomplexity

[Alex Vinokur]

Hi,

std::binary_search() takes logarithmic time on (sorted) container, but
returns bool, not iterator to the found element.

std::find() returns iterator to the found element, but takes linear
time.

Is there any way to get iterator to the found element on sorted
container in logarithmic time?

Alex Vinokur

 

[Thomas J. Gritzan]

Hi,

std::binary_search() takes logarithmic time on (sorted) container, but
returns bool, not iterator to the found element.

std::find() returns iterator to the found element, but takes linear
time.

Is there any way to get iterator to the found element on sorted
container in logarithmic time?

std::lower_bound, std::upper_bound, std::equal_range

 

[Maxim Yegorushkin]

std::binary_search() takes logarithmic time on (sorted) container, but
returns bool, not iterator to the found element.

std::find() returns iterator to the found element, but takes linear
time.

Is there any way to get iterator to the found element on sorted
container in logarithmic time?

It is:

template<class Iter, class T>
Iter binary_search_iter(Iter begin, Iter end, T val)
{
Iter i = std::lower_bound(begin, end, val);
return i != end && *i == val
? i // found
: end // not found
;
}