Modifikation der Binärsuche |
| 27.10.2009, 19:08 | Auf diesen Beitrag antworten » |
| lisischatz | Modifikation der Binärsuche Eine lineare Liste L[] der L¨ange n sei wie folgt teilsortiert: F¨ur alle Indizes k, l element {1, . . . , n} gilt a[k] > a[l] ->; k >gleich l - 1 Wenn also zwei Elemente in der falschen Reihenfolge stehen, dann steht das Gr¨oßere direkt vor dem Kleineren. Geben Sie eine m¨oglichst einfache Modifikation der Bin¨arsuche aus der Vorlesung an, die L[] auf das Vorhandensein eines gegebenen Schl¨ussels ¨uberpr¨uft. Die maximalen Kosten (Laufzeit) sollen in O(log n) liegen. das hatten wir noch nie in einer vorlesung und ich bin völlig hilflos, da wir es morgen früh abgeben müssen 
|
|
|
|
|
|