Given sorted vector find transition from negative to positive

Question

Given a sorted std::vector<int>, 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 unaryfind_if, which would facilitate this search (maybe in connection with the right lambda expression).

Answer 1

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)