Poszukiwanie ciągu liczbowego

Poszukiwanie ciągu liczbowego

Algorytmy przeszukiwania

---

Szukanie elementu

Często spotykanym rodzajem przeszukiwania jest wyszukiwanie elementu posiadającego pewną szczególną własność, jak np. najmniejszy, największy, podzielny przez jedenaście - element taki możemy nazwać idealnym.
Algorytm znajdowania elementu idealnego polega na wstępnym przyjęciu, że elementem idealnym jest pierwszy z dostępnych, a następnie na porównywaniu kolejnych elementów z elementem dotychczas uznanym za idealny. Jeśli podczas porównania okaże się, że element porównywany jest bliższy ideałowi niż dotychczasowy ideał, to wykonuje się zamianę przyjmując za ideał element aktualnie porównywany.
Poniższy fragment kodu znajduje w ciągu liczb podawanych przez użytkownikaliczbę największą:

Write('Podaj pierwsza liczbę ciągu = ');
ReadLn(Maksymalny);
For I:=2 To N Do
  Begin
    Write('Kolejna liczba = ');
    ReadLn(Liczba);
    If Liczba>Maksymalny Then Maksymalny:=Liczba;
  End;

Niżej przykłady programów szukających: podzielne, podzielne2, Ile_razy, liczby pierwsze.

---

Przeszukiwanie binarne

Przeszukiwanie binarne jest algorytmem sprawdzającym czy uporządkowany rosnąco ciąg liczbowy N-elementowy zawiera szukaną liczbę x (nazywane jest też przeszukiwaniem połówkowym).
Algorytm przeszukiwania binarego wykorzystuje uporządkowanie 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ą one 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, to znaczy, gdy start=stop.

  DANE:
     a - przeszukiwana tablica (posortowana rosnąco)
     x - poszukiwana liczba
     N - rozmiar tablicy
  WYNIK:
  prawda, jeżeli 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.

Oto rekurencyjna funkcja szukająca:

  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;