Witam!
Załóżmy że mam posortowana tablicę n elementową, wartości mogą się powtarzać.
Taka tablica może wyglądac np tak: [-23,-22, ... , 0, 2, 2, 6, ... , 9, 9, 9, 9, 9, ..., 127, 168, 456, ...].
Założmy że chcę wyszukać przedział w ktorym znajdują się dziewiątki, czyli index pierwszej i ostatniej 9.
Jak efektywnie to zrobić?
Ja robiłem to tak:
- Wyszukuję binarnie dowolną dziewiątkę.
- Wiedząc że tablica jest posortowana kolejne dziewiątki moga leżeć po prawej i po lewej stronie.
- za pomocą dwóch pętli while zliczam dziewiątki po prawej (pierwsza pętla while) i po lewej (druga pętla while).
Jednak jest to zbyt wolne, stąd moje pytanie jak od razu znaleźć przedział dziewiątek za pomocą wyszukiwania binarnego?