3 ms·
C++ has had a correct binary search in its standard library since c++98, and it works on pointers, integers etc, both signed and unsigned without overflows. I'm
by Jensson 4y ago
C++ has had a correct binary search in its standard library since c++98, and it works on pointers, integers etc, both signed and unsigned without overflows. I'm not sure why they say that this doesn't exist.
https://en.cppreference.com/w/cpp/algorithm/lower_bound https://en.cppreference.com/w/cpp/algorithm/lower_bound
- eesmith 4y agoI've lost track of the thread, because I don't know what you are talking about. Who is saying what doesn't exist? The lower_bound you pointed to takes start/end iterators defining the partially-ordered range to examine. The linked-to essay and the Wikipedia take array + size. These are different APIs. The latter - which is what this thread is about, IMO - is easier to implement because the sizes are always non-negative.
- froh 4y agorandom access iterators provide exactly the pointer into array semantics, with a difference type and jumping to a location in the range. https://en.cppreference.com/w/cpp/named_req/RandomAccessIterator https://en.cppreference.com/w/cpp/named_req/RandomAccessIter... they were conceived for c++'98 and transmogrified to a trait for c++20 the run time in GPs lower_bound link is log(n) for random access iterators and liner for non-random access.
- eesmith 4y agoYes. But how does that change my observation about the differences in the two APIs?