Atari Computer

Beispiel: Intervallhalbierung

Die folgenden Beispiele zeigen das Suchen in einem sortierten Feldern mittels Intervallhalbierung.

Sprache	C	Pascal	Modula
Beispiel	feldsuch.c	feldsuch.pas	feldsuch.mod

feldsuch.c

/* Suchen in einem sortierne Feld mit Intervallhalbierung ohne */
/* Test auf Exitenz. Da der Datentyp erst bei einer konkreten  */
/* Anwendung feststeht, ist der Sortieralgorithmus nur als     */
/* Beispiel und nicht als Modul programmiert.                  */

#define MAX_SORT_ELT 8000

typedef long SortKeyType;
typedef SortKeyType SortKeyArray[MAX_SORT_ELT];

int Such(SortKeyArray Feld, int Anz, SortKeyType Value)
{  int Min, Max, Mitte;

   Min = 0;
   Max = Anz-1;
   do {
      Mitte = Min + (Max - Min + 1) / 2;
      if (Value > Feld[Mitte])
      {
         Min = Mitte + 1;
      }
      else if (Value < Feld[Mitte])
      {
         Max = Mitte - 1;
      }
   } while (Feld[Mitte] != Value);
   return Mitte;
}

feldsuch.pas

(* Suchen in einem sortierne Feld mit Intervallhalbierung ohne *)
(* Test auf Exitenz. Da der Datentyp erst bei einer konkreten  *)
(* Anwendung feststeht, ist der Sortieralgorithmus nur als     *)
(* Beispiel und nicht als Modul programmiert.                  *)

const
   MaxSortElt = 8000;

type
   SortKeyType = long_integer;
   SortKeyArray = array[1..MaxSortElt] of SortKeyType;

function Such(var Feld:SortKeyArray; Anz:integer; Value:SortKeyType):integer;
var
   Min, Max, Mitte : integer;
begin
   Min := 1;
   Max := Anz;
   repeat
      Mitte := Min + (Max - Min) div 2;
      if (Value > Feld[Mitte]) then
      begin
         Min := Mitte + 1;
      end
      else if (Value < Feld[Mitte]) then
      begin
         Max := Mitte - 1;
      end;
   until (Feld[Mitte] = Value);
   Such := Mitte;
end;

feldsuch.mod

(* Suchen in einem sortierne Feld mit Intervallhalbierung ohne *)
(* Test auf Exitenz. Da der Datentyp erst bei einer konkreten  *)
(* Anwendung feststeht, ist der Sortieralgorithmus nur als     *)
(* Beispiel und nicht als Modul programmiert.                  *)

CONST
   MaxSortElt = 8000;

TYPE
   SortKeyType = LONGINT;
   SortKeyArray = ARRAY[1..MaxSortElt] OF SortKeyType;

PROCEDURE Such(VAR Feld:SortKeyArray; Anz:CARDINAL; Value:SortKeyType):CARDINAL;
VAR
   Min, Max, Mitte : CARDINAL;
BEGIN
   Min := 1;
   Max := Anz;
   REPEAT
      Mitte := Min + (Max - Min) DIV 2;
      IF (Value > Feld[Mitte]) THEN
         Min := Mitte + 1;
      ELSIF (Value < Feld[Mitte]) THEN
         Max := Mitte - 1;
      END;
   UNTIL (Feld[Mitte] = Value);
   RETURN Mitte;
END Such;

English version not yet available.