Jak powinien wyglądać dobry algorytm do wyszukiwania w posortowanym
ciągu? Można wyszukiwać binarnie lub metodą pełnego przeglądu.
Można także wyszukiwać interpolacyjnie. Każda z metod nadaje się
tylko do określonego przypadku. Metoda pełnego przeglądu jest
bardzo skuteczna dla małych ciągów. Interpolacyjne jest dobre
dla ogromnych ciągów dających się dobrze aproksymować jakąś
wzajemnie jednoznaczną funkcją. Wyszukiwanie binarne to stabilna
metoda, nawet pesymistycznie działa w czasie LogN, jednak
ma narzut liniowy. Zresztą interpolacyjne ma jeszcze większy
narzut.

Jak powinno wyglądać adaptatywne wyszukiwanie?

Czy może wyglądać tak: Pierwszy raz szukamy binarnie i
zapamiętujemy przybliżony czas. Potem szukamy metodą
pełnego przeglądu, jeśli czas jest większy, to
przerywamy i wyszukujemy binarnie. Potem z... nie
wiem ile... z 20 razy wyszukujemy binarnie, bo
działało najszybciej. Potem znowu jakaś próba... może z
wyszukiwaniem interpolacyjnym. Jeśli czas przekroczy
binarne, to przerywamy i znowu z 20 razy binarnie? Aha,
dane po każdym wyszukiwaniu mogą się zmienić co do
ilości i jakości.

Czy wystarczy zrobić to chamsko? Typu jeśli ilość danych
większa niż N to binarnie, a poza tym pełen przegląd?

Druga sprawa, czy interpoluje się tylko liniowo, czy
warto próbować jeszcze jakąś inną funkcją?

Pozdrawiam