0 Daumen
624 Aufrufe

Hi Community = ),

brauche dringend Hilfe bei der folgenden Aufgabe.

Führen Sie einen Korrektheitsbeweis für den Algorithmus zur binären Suche, d. h. zeigen Sie:

Die binäre Suche findet ein Element mit Schlüssel k in einem aufsteigend sortierten Array A, wenn A ein Element mit Schlüssel k enthält.

Gefragt von

hhu informatik 3 - algorithmen und datenstrukturen bei wanke.

frag doch lieber mal in einer übungsgruppe nach hilfe anstatt hier gefühlt nach jeder übungsaufgabe zu fragen.

Ich frage in meiner Übungsgruppe immer nach....danke für den Tipp...

Allerdings wurde uns das durch die Erkläungen (in 2 Übungsgruppen) nicht ganz klar sondern noch verschlimmert, da unser Übungsgruppenleiter auch etwas nervös ist und nicht allzu gut erklären kann. In der anderen hat man mir gesagt wäre es nicht viel besser. (Das kann ich aber nicht bestätigen, da ich zeitlich nur zu meiner Gruppe kann)

überleg dir, wie du es logisch darstellen und formalisieren kannst, dass bei binärer suche der gesuchte schlüssel irgendwann gefunden werden muss (entweder ist er auf dem vergleichselement oder in einer der beiden teilfolgen links bzw. rechts davon - du kannst zeigen dass die zu untersuchenden teilfolgen immer kleiner werden müssen.)
benutze dafür natürlich die in der aufgabenstellung gegebenenen informationen:
-die folge ist aufsteigend sortiert-der gesuchte schlüssel ist enthalten

Danke für die Hilfe = )

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...