Pole musí být před vyhledáváním seřazené.
Tato metoda rozděluje oblast, ve které hledá, na dvě půlky omezené levou stranou, pravou stranou a středem. Pokud je střed vyšší než hledaná hodnota, pravé omezení pole se sníží na index o jeden nižší, než je index středu. Pokud je ale nižší, levé omezení se zvýší na index o jeden vyšší, než je index středu. Střed se pak znovu vypočítá ( (Levé omezení + pravé omezení) DIV 2 ). Takto se jede, dokud se hledaná hodnota neobjeví na středu nebo dokud se nepřehodí levé a pravé omezení.
Funkce vrací 0, pokud hledaná hodnota nebyla nalezena (tj. pokud je levé omezení > pravé omezení), jinak vrací index, na kterém byla nalezena.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Type TIndex = 1..100; {Počet prvků pole = 100} TPole = Array[TIndex] of integer; {Vytvoření typu pole o 100 prvcích (číslech)} function binary_search(pole: TPole; n: TIndex; h: integer):word; var l, p, s : TIndex; {levé, pravé ohraničení, střed} begin l := 1; p := n; binary_search := 0; repeat s := (l+p) DIV 2; if (h < pole[s]) then p := s - 1 else l := s + 1; until (l > p) OR (h = pole[s]); if (h = pole[s]) then binary_search := s; end; |