---

Geschrieben von lisischatz am 27.10.2009 um 19:08:

  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