: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > działania na liczbach >

P R Z E S Z U K I W A N I E   B I N A R N E

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Przeszukiwanie binarne, zwane też połówkowym, jest algorytmem sprawdzającym czy uporządkowany rosnąco ciąg liczbowy zawiera podaną liczbę x.
Algorytm przeszukiwania binarnego korzysta z uporządkowania ciągu liczbowego dzieląc go każdorazowo na połowy. Poszukiwaną liczbę x porównuje się z liczbą środkową ciągu i w zależności od wyniku tego porównania przeszukiwana jest albo lewa, albo prawa część tablicy. Obszar poszukiwania wyznaczają dwa indeksy: start i stop oznaczające odpowiednio początek i koniec przeszukiwanego fragmentu tablicy - rozpoczynając przeszukiwanie zmiennym tym przypisujemy wartości start=1 i stop=n, zakończenie przeszukiwania następuje gdy przeszukiwany fragment tablicy zmaleje do jednego elementu, tj. gdy start=stop.

DANE:
  a      - przeszukiwana tablica (posortowana rosnąco)
  x      - poszukiwana liczba
  n      - rozmiar tablicy
WYNIK:
  prawda, jeśli tablica "a" zawiera liczbę "x"
  1. Przyjmij: start=1, stop=n

  2. Dopóki start<stop:

    • Wyznacz środek przedziału sr=(start+stop) Div 2,

    • Jeżeli poszukiwana liczba x jest nie większa niż liczba w środku tablicy, to odrzuć prawą jej część przyjmując za stop=sr,

    • W przeciwnym wypadku odrzuć część lewą przyjmując za start=sr+1,

  3. Teraz start=stop, zwróć prawdę jeśli a[start]=x.

Type
  Tablica = Array[1..1000] Of Integer;

Function Szukaj(Var a : Tablica; x, n : Integer) : Boolean;
Var
  start, stop, sr : Integer;
Begin
  start:=1;
  stop:=n;
  While start<stop Do
    Begin
      sr:=(start+stop) Div 2;
      If x<=a[sr] Then stop:=sr
      Else start:=sr+1;
    End;
  Szukaj:=(a[start]=x);
End;

Pomimo, iż na ogół algorytm rekurencyjny jest gorszy od iteracyjnego, warto tutaj przytoczyć definicję rekurencyjną funkcji Szukaj przeszukującej binarnie uporządkowaną tablicę liczb:

DANE:
  a           - przeszukiwana tablica (posortowana rosnąco)
  x           - poszukiwana liczba
  start, stop - przeszukiwany fragment tablicy
WYNIK:
  prawda, jeśli tablica "a" zawiera liczbę "x"
  1. Jeżeli start=stop, to zwroć prawdę gdy a[start]=x,

  2. W przeciwnym wypadku:

    • Wyznacz środek przedziału sr=(start+stop) Div 2,

    • Jeżeli poszukiwana liczba x jest nie większa niż liczba w środku tablicy, to przeszukaj lewą część tablicy,

    • W przeciwnym wypadku przeszukaj prawą część.

Type
  Tablica = Array[1..1000] Of Integer;

Function Szukaj(Var a : Tablica; x, start, stop : Integer) : Boolean;
Var
  sr : Integer;
Begin
  If start=stop Then Szukaj:=(a[start]=x)
  Else
    Begin
      sr:=(start+stop) Div 2;
      If x<=a[sr] Then Szukaj:=Szukaj(a, x, start, sr)
      Else Szukaj:=Szukaj(a, x, sr+1, stop);
    End;
End;