Wyszukiwanie binarne wymaga dostępu do dowolnego elementu w czasie stałym, czego listy nie udostępniają. Zaimplementowanie wyszukiwania binarnego (praktycznie taki sam algorytm jest do zwracania elementów, jak i do stwierdzania obecności) na tych listach co podałeś da złożoność obliczeniową O(n).
Hmm, na pewno? Nie przemyślałem tego dobrze, ale jak dla mnie wyszukiwanie binarne (a raczej symulowanie wyszukiwania binarnego na listach) ma
Lista jednokierunkowa - O(n ^ 2).
Dlaczego:
Szukanie liczby 8, lista jednokierunkowa:
1 2 3 4 5 6 7 8 9 10 11
przejście do środkowego elementu (6) + przejście do elementu 9 - O(n)
przejście do elementu 8 (albo 7 a następnie 8) - od początku listy... kolejne O(n)
Lista dwukierunkowa - sam nie wiem, strzelałbym O(n log n) (to samo szukanie co poprzednio z tym że każde kolejne szukanie to max log x operacji (x to poprzednia ilość operacji)
edit: rozpędziłem się z tymi obliczeniami, poniższy post zawiera 'poprawki' mojego toku myślenia.