Potrzebuję binarnego algorytmu wyszukiwania, który jest kompatybilny z kontenerami C ++ STL, coś std::binary_search
w rodzaju <algorithm>
nagłówka biblioteki standardowej , ale potrzebuję go do zwrócenia iteratora wskazującego na wynik, a nie prostej wartości logicznej informującej mnie, czy element istnieje.
(Na marginesie, o czym myślała do cholery standardowa komisja, definiując API dla binary_search ?!)
Moim głównym zmartwieniem jest to, że potrzebuję szybkości wyszukiwania binarnego, więc chociaż mogę znaleźć dane za pomocą innych algorytmów, jak wspomniano poniżej, chcę wykorzystać fakt, że moje dane są sortowane, aby uzyskać korzyści z binarnego wyszukiwanie, a nie wyszukiwanie liniowe.
do tej pory lower_bound
i upper_bound
niepowodzenie, jeśli brakuje odniesienia:
//lousy pseudo code
vector(1,2,3,4,6,7,8,9,0) //notice no 5
iter = lower_bound_or_upper_bound(start,end,5)
iter != 5 && iter !=end //not returning end as usual, instead it'll return 4 or 6
Uwaga: mogę również używać algorytmu, który nie należy do przestrzeni nazw std, o ile jest zgodny z kontenerami. Powiedzmy boost::binary_search
.