Hoe vind je op de meest efficiënte manier een waarde in een gesorteerde C++-vector?

Ik heb gekeken naar vindenen binary_search, maar find maakt geen gebruik van het feit dat de vector is gesorteerd, en binary_search retourneert alleen een true of false, niet waar het de waarde vond. Is er een functie die mij het beste van twee werelden kan bieden?

Antwoord 1, autoriteit 100%

Je kunt find gebruiken om een ​​bepaald element in een container in tijd O(N) te lokaliseren. Met vector kunt u willekeurige toegang uitvoeren en profiteren van de klasse lower_bound (log2(N)), upper_bound of equal_range van std-algoritmen. std::lower_bounddoet dat voor je. Het staat in het gedeelte met equivalent gedrag bovenaan voor binary_search. Het nut van binary_search is echter beperkt tot ja en nee antwoorden (misschien moet de naamgeving worden verbeterd in de toekomstige versie van C++; binary_in()).

Antwoord 2, autoriteit 36%

Er is een methode, std::equal_range, die u een paar geven met de onder- en bovengrens van de subset met de gewenste waarde. Als beide items in het paar identiek zijn, bestaat de waarde die u zocht niet.

Antwoord 3, autoriteit 11%

template<class T, class U>
bool contains(const std::vector<T>& container, const U& v)
{
    auto it = std::lower_bound(
        container.begin(),
        container.end(),
        v,
        [](const T& l, const U& r){ return l < r; });
    return it != container.end() && *it == v;
}