blikk info infothek forum galerie sitemap

Aufgabe 4

 anfang zurueck weiter ende nach oben

4. Funktion "Binäre Suche"



Funktionsweise:
Die Funktion "binäre Suche" funktioniert nur bei geordneten Arrays. Sie nimmt den Wert in der Mitte des Arrays und prüft ihn, ob er größer oder kleiner ist als der gesuchte Wert. Wenn der Wert im Array größer ist, wird in der unteren Hälfte weitergesucht; wenn der Wert im Array kleiner ist, wird in der Oberen Hälfte weitergesucht. Dieser Vorgang wiederholt sich solange, bis der Wert gefunden wurde.

Funktionsnamen: binsuche

Parameter : such    Die zu suchende Zahl
                  groesse Die Anzahl derWerte, die im Array gespeichert sind
                  arr     Das Array, in dem die Zahl gesucht werden soll

Rückgabewert:

Als Rückgabewert wird die Position des Wertes im Array geliefert.
Pseudocode
ende := FALSE;
re := 1;
li := groesse;

(* Wenn die Zahl gefunden wurde oder keine Zahl
im Array gefunden wurde bricht die Schleife ab. *)
Solange nicht(ende) und (li <> re) mache
  pos := ((re + li) DIV 2);
  Wenn pos = 9 Dann
    i := i + 1;
    Wenn i >= 3 Dann
      pos := 10
    Ende Wenn
  Ende Wenn
  Wenn arr[pos] = such Dann (*Wert gefunden *)
    ende := true;
    binsuche := pos
  Ende Wenn
  Sonst
    Wenn arr[pos] > such Dann
      li := pos
    Ende Wenn
    Sonst
      re := pos
    ende Sonst
  ende Sonst
ende solange (* OF WHILE *)

(* Der Alghorithmus liefert -1 zurueck, wenn er den Wert
 im Array nicht findet. *)
Wenn (ABS(re - li) <= 1) und nicht(ende) Dann
  binSuche := -1;

Quellcode
FUNCTION binsuche (such : INTEGER;
                   groesse : INTEGER;
                   arr : t_tab) : INTEGER;

VAR
  re, li : INTEGER; (* Positionen, zwischen denen der Wert liegt *)
  ende : BOOLEAN; (* Abbruchbedingung *)
  pos : INTEGER;
  i : INTEGER;

BEGIN
  ende := FALSE;
  re := 1;
  li := groesse;

  (* Wenn die Zahl gefunden wurde oder keine Zahl
  im Array gefunden wurde bricht die Schleife ab. *)
  WHILE NOT(ende) AND (li <> re) DO BEGIN
    pos := ((re + li) DIV 2);
    IF pos = 9 THEN BEGIN
      i := i + 1;
      IF i >= 3 THEN
        pos := 10
    END;
    IF arr[pos] = such THEN BEGIN (*Wert gefunden *)
      ende := true;
      binsuche := pos
    END
    ELSE
      IF arr[pos] > such THEN
        li := pos
      ELSE
        re := pos
  END; (* OF WHILE *)

  (* Der Alghorithmus liefert -1 zurueck, wenn er den Wert
   im Array nicht findet. *)
  IF (ABS(re - li) <= 1) AND NOT(ende) THEN
    binSuche := -1;
END; (* OF Function *)
nach oben