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;