Wyszukiwanie liniowe z wartownikiem


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych

 

Problem

W n-elementowym zbiorze Z wyszukać element posiadający pożądane własności.

 

 

W algorytmie wyszukiwania liniowego sprawdzamy kolejne elementy zbioru aż do napotkania jego końca lub poszukiwanego elementu. Zachodzi pytanie, czy algorytm ten można przyspieszyć. Aby na nie odpowiedzieć, zapiszmy algorytm w poniższej postaci:

Wejście
n     liczba elementów w tablicy Z, n N
Z  – tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n-1
k  – poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z
Wyjście:

pozycja elementu zbioru Z o kluczu k lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z. i C

 

Numer Operacja
1 i ← 0
2 Jeśli in, to zakończ z wynikiem -1
3 Jeśli Z[i] = k, to zakończ z wynikiem i
4 ii + 1
5 Idź do 2

 

Sprawdzimy teraz ile operacji wykonuje ten algorytm w dwóch charakterystycznych przypadkach:

Przypadek pierwszy: poszukiwanej liczby nie ma w zbiorze. Poniżej przedstawiamy liczbę wykonań poszczególnych operacji w algorytmie:

 

Numer Operacja Liczba wykonań
1 i ← 0 1
2 Jeśli in, to zakończ z wynikiem -1 n + 1
3 Jeśli Z[i] = k, to zakończ z wynikiem i n
4 ii + 1 n
5 Idź do 2 n
  RAZEM: 4n + 2

 

Przypadek drugi: poszukiwana liczba statystycznie znajduje się w środku zbioru – czasem znajdziemy ją wcześniej, a czasem później, zatem średnio będzie w środku.

 

Numer Operacja Liczba wykonań
1 i ← 0 1
2 Jeśli in, to zakończ z wynikiem -1 n/2 + 1
3 Jeśli Z[i] = k, to zakończ z wynikiem i n/2 + 1
4 ii + 1 n/2
5 Idź do 2 n/2
  RAZEM: 2n + 3

 

Zwróć uwagę, iż w każdym obiegu pętli nasz algorytm wykonuje dwa testy – w instrukcji numer 2 i 3. Usprawnienie pracy algorytmu będzie polegało na eliminacji testu 2. Jednakże test ten jest niezbędny, aby zakończyć przeglądanie tablicy w przypadku, gdy poszukiwanego elementu nie ma w zbiorze. Skoro tak, to wstawmy poszukiwany element na koniec zbioru, wtedy test 2 stanie się zbędny, nieprawdaż. Algorytm w zmienionej postaci wygląda następująco:

 

Numer Operacja
1a Z[n] ← k
1b i ← 0
2 usunięta
3 Jeśli Z[i] = k, to idź do 6
4 ii + 1
5 Idź do 3
6 Jeśli i = n, to zakończ z wynikiem -1
7 Zakończ z wynikiem i

 

Zmiany w stosunku do pierwotnego algorytmu są następujące:

1a – instrukcja umieszcza na końcu zbioru Z poszukiwany element o wartości k. Dzięki tej operacji dostajemy gwarancję, iż zawsze znajdziemy w zbiorze element k.

2 – test osiągnięcia końca zbioru stał się zbędny, ponieważ element o wartości k zawsze znajdziemy w zbiorze.

3, 6, 7 – znalezienie elementu o wartości k wymaga sprawdzenia, czy nie jest on elementem wstawionym do zbioru w operacji 1a. Jeśli tak, to zbiór faktycznie nie zawierał poszukiwanego elementu.

 

Przypadek pierwszy: poszukiwanej liczby nie ma w zbiorze. Poniżej przedstawiamy liczbę wykonań poszczególnych operacji w algorytmie:

 

Numer Operacja Liczba wykonań
1a Z[n] ← k 1
1b i ← 0 1
2    
3 Jeśli Z[i] = k, to idź do 6 n + 1
4 ii + 1 n
5 Idź do 3 n
6 Jeśli i = n, to zakończ z wynikiem -1 1
7 Zakończ z wynikiem i 0
  RAZEM: 3n + 4

 

Przypadek drugi: poszukiwana liczba statystycznie znajduje się w środku zbioru – czasem znajdziemy ją wcześniej, a czasem później, zatem statystycznie będzie w środku.

 

Numer Operacja Liczba wykonań
1a Z[n] ← k 1
1b i ← 0 1
2    
3 Jeśli Z[i] = k, to idź do 6 n/2 + 1
4 ii + 1 n/2
5 Idź do 3 n/2
6 Jeśli i = n, to zakończ z wynikiem -1 1
7 Zakończ z wynikiem i 1
  RAZEM: 3/2n + 5

 

Porównajmy teraz wyniki z pierwszej i drugiej wersji algorytmu w poniższej tabelce (wartości ułamkowe z ostatniej kolumny należy rozumieć jako wartości statystyczne).:

 

n Przypadek pierwszy Przypadek drugi
Algorytm
podstawowy
Algorytm
usprawniony
Algorytm
podstawowy
Algorytm
usprawniony
4n + 2 3n + 4 2n + 3 3/2n + 5
1 6 7 5 6,5
2 10 10 7 8
3 14 13 9 9,5
4 18 16 11 11
5 22 19 13 12,5
6 26 22 15 14
... ... ... ... ...
10 42 34 23 20
100 402 304 203 155
1000 4002 3004 2003 1505
10000 40002 30004 20003 15005
... ... ... ... ...

 

Chociaż początkowo algorytm pierwszy wygrywa w ilości operacji, to przy wzroście liczby elementów zbioru widzimy wyraźnie, iż algorytm usprawniony wykonuje mniej operacji (począwszy od n > 3), zatem działa szybciej.

Opisana metoda wyszukiwania nosi nazwę wyszukiwania liniowego z wartownikiem (ang. Search with Sentinel). Wartownikiem jest dodany na końcu zbioru element równy poszukiwanemu. Dzięki niemu uzyskujemy zawsze pewność znalezienia poszukiwanego elementu w zbiorze. Jeśli jest to wartownik, to elementu poszukiwanego w zbiorze nie ma i zwracamy pozycję -1. Jeśli nie jest to wartownik, to znaleźliśmy poszukiwany element w zbiorze i zwracamy jego pozycję i.

Należy podkreślić, iż wyszukiwanie z wartownikiem można stosować tylko wtedy, gdy do zbioru da się dołączyć jeszcze jeden element.

 

Algorytm wyszukiwania liniowego z wartownikiem

Wejście
n      liczba elementów w tablicy Z, n N
Z  – tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n. Ostatnia pozycja Z[n] będzie zajęta przez wartownika, zatem nie może być używana do innych celów.
p  – indeks pierwszego elementu Z, od którego rozpoczniemy poszukiwania. p C
k  – poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z
Wyjście:

Pozycja elementu zbioru Z o kluczu k lub -1 w przypadku nie znalezienia elementu.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z. i C
Lista kroków:
K01: Z[n] ← k ; na końcu zbioru umieszczamy wartownika
K02: ip ; przeszukiwanie rozpoczynamy od pozycji p
K03: Jeśli Z[i] = k, to idź do K06 ; sprawdzamy kolejne elementy zbioru
K04: ii + 1 ; jeśli element nie znaleziony, przechodzimy do następnego elementu w zbiorze
K05: Idź do K03  
K06: Jeśli i = n, to zakończ z wynikiem -1 ; sprawdzamy, czy znaleziony element jest wartownikiem
K07: Zakończ z wynikiem i ; jeśli nie, to zwracamy pozycję znalezionego elementu

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje z pierwszego wiersza liczbę n. Z następnych n wierszy odczytywane jest n danych całkowitych. W ostatnim wierszu odczytywana jest liczba k, którą należy wyszukać wśród podanych n liczb. Program wypisuje numer pozycji w odczytanym ciągu liczb, na której znajduje się liczba k lub -1, jeśli liczby nie odnaleziono.

 

Lazarus
// Wyszukiwanie liniowe z wartownikiem
// Data:   27.04.2008
// (C)2012 mgr Jerzy Wałaszek
//---------------------------

program prg;

type Tint = array of integer;

function Szukaj(var T : Tint; n,k,p : integer) : integer;
var i : integer;
begin
  T[n] := k;
  i := p;
  while T[i] <> k do inc(i);
  if i = n then Szukaj := -1 else Szukaj := i;
end;

var
  T : Tint;
  n,k,i: integer;

begin
  readln(n);
  SetLength(T,n + 1);
  for i := 0 to n - 1 do readln(T[i]);
  readln(k);
  writeln;
  writeln(Szukaj(T,n,k,0));
  writeln;
  SetLength(T,0);
end.
Code::Blocks
// Wyszukiwanie liniowe z wartownikiem
// Data:   26.04.2008
// (C)2012 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

int Szukaj(int T[], int n, int k, int p)
{
  int i;

  T[n] = k;
  for(i = p; T[i] != k; i++) ;
  if(i == n) return -1; else return i;
}

int main()
{
  int * Z,n,k,i;
  
  cin >> n;
  Z = new int [n + 1];
  for(i = 0; i < n; i++) cin >> Z[i];
  cin >> k;
  cout << endl << Szukaj(Z,n,k,0) << endl << endl;
  delete [] Z;
  return 0;
}
Free Basic
' Wyszukiwanie liniowe z wartownikiem
' Data:   27.04.2008
' (C)2012 mgr Jerzy Wałaszek
'---------------------------

Function Szukaj(T As Integer Ptr, n As Integer, k As Integer, p As Integer) As Integer
  Dim i As Integer
  T[n] = k
  i = p
  While T[i] <> k: i += 1: Wend
  If i = n then Szukaj = -1 Else Szukaj = i
End Function

Dim T As Integer Ptr
Dim As Integer n,k,i

Open Cons For Input As #1

Input #1,n

T = New Integer [n+1]

For i = 0 To n - 1
  Input #1,T[i]
Next
  
Input #1,k

Close #1

Print
Print Szukaj(T,n,k,0)
Print

Delete [] T

End
Wynik
5
13
18
954
235
12
111

-1

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.