Menu schließen

Modifikation der Binärsuche

Frage: Modifikation der Binärsuche
(2 Antworten)

 
Eine lineare Liste L[] der Lšange n sei wie folgt teilsortiert: Fšur alle Indizes k, l ∈ {1, . . . , n} gilt

a[k] > a[l] ⇒ k ≥ 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.

ich kapier da garnix...also was die groß O notation ist weiss ich mittlerweile aber kann mit info sonst nix anfangen.
GAST stellte diese Frage am 27.10.2009 - 16:04

 
Antwort von GAST | 27.10.2009 - 16:06
äh tschuldigung: soll heißen : k,
l ∈ {1, . . . , n} gilt a[k]>a[l]->k >gleich l-1


Autor
Beiträge 0
13
Antwort von track (ehem. Mitglied) | 02.11.2009 - 22:46
keine ahnug nwas ihr in der vorlesung gemacht habt, aber das musst du wohl die binär suche etwas änderen, damit dieser algorithmus auch hier funktioniert :)

Verstoß melden
Hast Du eine eigene Frage an unsere Informatik-Experten?

> Du befindest dich hier: Support-Forum - Informatik