Warum ist die binäre Suche bei der verketteten Liste nicht so effektiv?

[Kelsjb7]

Klar, ich habe keinen Index, aber trotzdem, ist es ja so, bin ich einmal zur Mitte gegangen und habe geschaut, ob mein Element dort vorhanden ist, kann ich ja alle Elemente links von meiner verketteten Liste nicht mehr beachten und rechts weiter machen? Auch wenn ich nicht direkt zur Mitte springen kann oder nicht?

 

[mihe7]

Effektiv ist er genauso, er ist nur nicht so effizient. Jede "Bewegung" in der verketteten Liste ist eine "Elementaroperation", die Du berücksichtigen musst. Du gehst bis zur Mitte und damit hast Du alleine dafür n/2 Operationen, womit der Algorithmus auch schon in O(n) liegt, also lineare Laufzeit hat. Daher ist er weit weniger effizient als ein Algorithmus mit logarithmischer Laufzeit.

Nachtrag: zum Vergleich mal eine Liste mit 1024 Einträgen. Bei der verketteten Liste musst Du schon 512 Schritte ausführen, um bis zur Mitte zu gelangen. Im Array brauchst Du max. 10 Schritte, um die Suche komplett durchzuführen.

 

[LimDul]

Das Problem mit der binären Suche bei einer verketteten Liste ist, dass sie langsamer ist, als eine lineare Suche. Du musst so oder so bei der verketteten Liste vom Anfang bis zum gesuchten Element gehen. Wenn du aber binär suchst und dann gesuchtes Element steht an der ersten Position, dann läufst du trotzdem erst zur Mitte um dann wieder zum Anfang zurück zu laufen. Das ist schlicht imperformant.

 

[Mart]

angenommen dein Element liegt links an position 1 -> du gehst zur mitte -> ghest nach links dann hast du wieder alle Elemente durchlaufen
angenommen dien Elment liegt an posiition n -> du gehst zur mitte -> gehst nach rechts dann hast du wieder alle elemente durchlaufen

somit somit ist dein
BESTCASE: element ist in der mitte mit n/2
MIDDLE CASE: (der meistens weniger aussagt) irgendwo bei n/2 + irgendways < n/2
WORST CASE: du latscht alles durch ... also n

der unterschied ist nun -> latscht du einfach durch ändert sich dein bestcase auf 1 da du im allerbesten fall gleich am anfang das element findest
dein Middlecase wird zu n/2
und der worstcase bleibt gleich

somit mitte latschen und dann suchen Effizient < einfach linear suchen Effizienz


für "Effizienz" ist der Worstcase und bestcase am aussagekräftigsten, aber der middle case existiert auch nicht ohne grund