Przeszukiwanie binarne, pytanie

[józef92]

Jaki jest koszt pesymistyczny mierzony liczbą operacji listowych dla algorytmu wyszukiwania binarnego zaimpelemntowanego na n-elementowej:

a) liście jednokierunkowej;
b) liście dwukierunkowej


Co do samego przeszukiwania to wiem, że stwierdza on w czasie logrytmicznym czy dany element znajduje sie na liscie uorzadkowanej czy tez nie.

[argv]

Moim zdaniem nie da się szybciej niż \(\displaystyle{ O(n)}\) bo trzeba chociażby ustalić ile jest elementów na liście. Pomijając pomysł bs na listach tego typu, logarytmicznie pesymistycznie da się tylko jeśli zrobimy sobie dodatkową tablicę wskaźników na elementy listy i na niej bedziemy zapuszczać bs albo użyjemy skip-listy i dostaniemy oczekiwany logarytmiczny, ale to już takie przemyślenia poza konkursem.

[józef92]

No na jednokierunkowej O(n) tak myślałem, a na dwukierunkowej nie będzie \(\displaystyle{ O(n^2)}\)???

[Althorion]

Na pewno na dwukierunkowej nie może być wolniej, gdyż wystarczy zignorować jeden z kierunków i postępować tak, jak na liście jednokierunkowej.

[józef92]

W sumie rację nie potrzebnie brałem jeszcze przeszukiwanie poprzedników.