Podany posortowany wektor znajduje przejście z ujemnego do dodatniego

Question

Biorąc pod uwagę sortowane std::vector<int>, chciałbym, za pomocą funkcji C++ 11-STD, znaleźć indeks, w którym elementy przejść od negatywnego do pozytywnego.

Mam świadomość, że mogę to zaimplementować za pomocą wyszukiwania binarnego, ale jestem zainteresowany, czy istnieje jakakolwiek funkcja w standardowej bibliotece, podobna do unarnej find_if, która ułatwiłaby to wyszukiwanie (być może w połączeniu z prawidłowym wyrażeniem lambda).

Answer 1

należy znaleźć lower_bound od 0:

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

otrzymany iterator będzie wskazywać na najbliższym miejscu, gdzie można wstawić 0 bez zakłócania kolejność elementów. Podobnie, upper_bound zwróci najbardziej prawy taki iterator.

runtime algorytmu jest O(logN)