Search code examples
c++c++11searchstlstl-algorithm

Given sorted vector find transition from negative to positive

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).

Solution

  • 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)