Bináris keresés (algoritmus)

Átirányítás ide:

• Logaritmikus keresés (algoritmus)

A kereséshez szükséges iterációk száma a bináris kereséssel csökkenthető,azonban ehhez a tömb elemeinek növekvő sorrendben kell lenniük.A bináris keresés egyike a leggyorsabb keresési algoritmusoknak,ami minden egyes iteráció esetében a vizsgálandó elemek számát felére csökkenti mindaddig amíg a kívánt rekordot megtalálja. Nézzünk példát a bináris keresést megvalósító eljárásra Pascalban:

{
-= Leírás =-
Ez a rutin a Values tömbben megkeresi a DesiredValue változóban megadott értéket.
A Found változót pedig igazra (True) állítja b,a MidInd változó pedig az
indexértékeket tartalmazza.
Ellenkező esetben a Found változó értéke hamis (False)

-= Paraméterek =-
Values:(bemenő adat)       : A tömb,amiben a keresést végezzük.
LowInd:(bemenő adat)       : A keresési tartomány legalsó eleme.
HighInd:(bemenő adat)      : A keresési tartomány legfelső eleme.
DesiresValue:(bemenő adat) : Az érték amit keresünk.
MidInd:(kimenő adat)       : A tömb aktuális indexe.
Found:(kimenő adat)        : Igaz,ha az előírt értéket a rutin megtalálta,egyébként hamis.

-= Szükséges Típusok =-
ArrayType                  : A tömb típusa.
ArrayElement               : A tömb elemeinek típusa.

-= Eljárás hívására példa =-
BinarySearch(Values,1,10,15,Location,Found);
}
BinarySearch(Values:ArrayType;
             LowInd,HighInd:Integer;
             DesiredValue:ArrayElement;
             Var MidInd:Integer;
             Var Found:Boolean);
Begin
  Found:=False;
  MidInd:=(HighInd + LowInd) Div 2;
  While ((Not Found) And (HighInd >= LowInd)) Do Begin
    If (Values[MidInd] = DesiredValue) Then Found:=True
    Else If (Values[MidInd] > DesiredValue) Then HighInd:=MidInd - 1
         Else LowInd:=MidInd + 1;
    MidInd:=(HighInd + LowInd) Div 2;
  End;
End;