user695652 user695652 - 1 year ago 56
C++ Question

Given sorted vector find transition from negative to positive

Given a sorted

, I would like, using C++11-STD functions, to find the index where the elements transition from negative to positive.

I am aware that I can implement this using a binary search but I am interested if there is any function in the standard library, similar to the unary
, which would facilitate this search (maybe in connection with the right lambda expression).

Answer Source

You should find the lower_bound of 0:

auto iter = std::lower_bound(vec.begin(), vec.end(), 0);

the resulting iterator will point to the earliest position where you can insert 0 without disrupting the ordering of elements. Similarly, upper_bound will return the right-most such iterator.

The runtime of the algorithm is O(logN)