Delphi » Gotowce

Przeszukiwanie binarne posortowanej tablicy

Pawlik67

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 :-)

Gotowce

0 komentarzy