Home » Tipps & Tricks » Algorithmen » Suchen » Binäre Suche

Binäre Suche

Wenn das Array sortiert vorliegt, sodass das erste Element das kleinste ist, kann die Binäre Suche durchgeführt werden, um einen bestimmten Wert in einem Array zu suchen.

So lässt sich in einem Telefonbuch, indem die Einträge sortiert sind, deutlich schneller die richte Rufnummer finden, als in einem unsortierten. Sind die Werte sortiert, wird in der Mitte des Arrays angefangen zu suchen. Im besten Fall findet man das Element sofort, ansonsten kann mit dem Wert verglichen werden: Ist der zu findende Wert größer, ist das Ziel-Element auf jeden Fall über dem mittleren Element. Ist er kleiner, ist das Ziel-Element darunter. Nach diesem Durchlauf fällt also die Hälfte der möglichen Elemente weg, da sich das Ziel-Element entweder in der ersten oder zweiten Hälfte des Arrays befindet. Dann wird der Vorgang wiederholt: Von der jeweiligen Hälfte wird wieder das mittlere Element genommen, und wieder verglichen, ob der Wert größer oder kleiner ist. So schränkt sich der mögliche Bereich, indem sich das Zielelement befindet, immer mehr ein, genauer halbiert er sich bei jedem Durchlauf. Das Ziel-Element ist spätestens dann gefunden, wenn die mögliche Menge genau ein Element enthält. Der schlechteste Fall ist somit der Logarithmus der Länge des Arrays zur Basis 2. Das Verfahren benötigt somit deutlich weniger Durchläufe als die lineare Suche, um einen bestimmten Wert zu finden, gerade bei größeren Mengen rentiert es sich daher.

Folgende Funktion sucht einen Wert in einem sortiertem Array:

type
  TIntArray: array [0..100] of Integer;

function FindInSortedArray(AArray: TIntArray; AValue: Integer): Integer;
var
  Pivot, LeftBound, RightBound: Integer;
begin
  Result := -1;
  LeftBound := 0;
  RightBound := High(AArray);
  repeat
    Pivot := (LeftBound + RightBound) div 2;
    if AValue > AArray[Pivot] then
      LeftBound := Pivot + 1
    else if AValue  RightBound);
  if AArray[Pivot] = AValue then
    Result := Pivot;
end;