Programowanie w języku Delphi » Gotowce

Przeszukiwanie binarne posortowanej tablicy

   Znaczna większość programów opiera się na wyszukiwaniu i przetwarzaniu danych zawartych w tablicach. Chcielibyśmy aby program szybko odnalazł pozycję szukanego elementu w naszych danych. Wówczas zastanawiamy się jak napisać algorytm aby takie zamierzenie uzyskać. Poniżej przedstawiam dwie metody wyszukiwania pozycji dla szukanego elementu. W opisanych metodach nasze dane zostaną przekazane po przez paramatr funkcji iTabela , w której wszystkie elementy będą typu Integer.

Pierwszym sposobem na przeszukiwanie tabeli jest metoda porównywania kolejnych komórek tabeli z wartością poszukiwaną, poczynając od najmniejszego wskaźnika a kończąc na ostatnim. Jest to metoda, którą możemy użyć w przypadku kiedy nasze elementy w tabeli są nieposortowane jak i również kiedy są one posortowane.

Oto kod takiej funkcji gdzie parametrami są :
iTabela   – Tablica dynamiczna z elementami typu Integer,
ZnajdzElement – Wartość typu Integer szukanego elementu, który chcemy znaleźć.

Wynikiem funkcji PozycjaElementu będzie wartość –1 gdy ZnajdzElement nie istnieje w iTabela lub wartość z przedziału 0...Maksymum Elementów iTabela wskazująca na szukany element.

Function  PozycjaElementu(Const ZnajdzElement : Integer; Var iTabela : Array Of Integer) : Integer;
 
Var  
    Max, Min : Integer;
    Wskaznik : Integer;
 
 Begin
   Min := Low(iTabela); // Minimalny wskaźnik iTabela
   Max := High(iTabela); // Maksymalny wskaźnik iTabela
   Wskaznik := Min; //Wskaźnik aktualnie badanego elementu iTabela
 
  Repeat   
 
   If iTabela[Wskaznik] = ZnajdzElement  //Element istnieje w iTabela
      Then Begin
               PozycjaElementu := Wskaznik; //To jest pozycja szukanego elementu
               Exit;
              End;
    Inc(Wskaznik); //Zwiększenie Wskaźnika o 1
 
  Until (Wskaznik>Max);
 
    //Element nie istnieje w iTabela
    PozycjaElementu  := -1;
 
 End; { koniec funkcji }


   W przypadku kiedy wartości w iTabela są posortowane korzystniejszą i szybszą może okazać się metoda „Dziel i sprawdzaj”. Zasada działania polega na ustalaniu wartości Min i Max między którymi nasz element szukany może się znajdować. Na podstawie tych wartości ustalany jest Wskaznik, który będzie znajdował się w połowie Min i Max . Stąd nazwa metody „Dziel i sprawdzaj”. Jeśli wartość iTabela[Wskaznik] będzie większa od wartości szukanego elementu ( ZnajdzElement ) to wartość Max zostanie przesunięta do wartości Wskaznik-1 . W przeciwnym przypadku wartości Min zostanie przypisana nowa wartość Wskaznik+1 . W ten sposób zawęża się zakres w którym element szukany powinien się znajdować i ustalany jest nowy Wskaznik dla iTabela . Proces ten będzie trwał dopóki element nie zostanie znaleziony lub pole w którym miałby być ustalony Wskaznik nie będzie wartością ujemną
( Until (Max-Min<0) ).

Function  PozycjaElementu(Const ZnajdzElement : Integer; Var iTabela : Array Of Integer) : Integer;
 
 Var   
   Max, Min : Integer;
   Wskaznik : Integer;
 
 Begin
   Min := Low(iTabela);
   Max := High(iTabela);
   Wskaznik := Min + ((Max - Min) Div 2); //Ustalenie pozycji Wskaźnika w połowie iTabela
 
  Repeat
 
   If iTabela[Wskaznik] = ZnajdzElement  //Element istnieje w iTabela
      Then Begin  
              PozycjaElementu := Wskaznik; //To jest pozycja szukanego elementu
              Exit;
              End;
   If  iTabela[Wskaznik] > ZnajdzElement
       Then Max := Wskaznik-1
       Else  Min := Wskaznik+1;
 
    //Tu obliczamy, który wskaźnik tabeli będzie aktualnie sprawdzany
    Wskaznik := Min + ((Max - Min) Div 2); 
 
  Until (Max-Min<0);
 
    //Element nie istnieje w iTabela
    PozycjaElementu := -1;
 
End; { koniec funkcji }


Życzę owocnego szukania :-)