Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie liniowe z wartownikiem

SPIS TREŚCI
Tematy pomocnicze

Problem

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

Rozwiązanie

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:

Algorytm wyszukiwania liniowego

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.

Elementy pomocnicze:

i : przebiega przez kolejne indeksy elementów Z. i ∈ C.
Numer Operacja
  1
i ← 0
  2
Jeśli i ≥ n,
to zakończ z wynikiem -1
  3
Jeśli Z[i] = k,
to zakończ z wynikiem i
  4
i ← i + 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 i ≥ n,
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 i ≥ n,
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
i ← i + 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:

: 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 nieznalezienia elementu.

Elementy 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, ; sprawdzamy kolejne elementy zbioru
     to idź do K06
K04: i ← i + 1 ; jeśli element nie znaleziony,
               ; przechodzimy do następnego elementu w zbiorze
K05: Idź do K03
K06: Jeśli i = n, ; sprawdzamy, czy znaleziony element
     to zakończ z wynikiem -1 ; jest wartownikiem
K07: Zakończ z wynikiem i     ; jeśli nie, to zwracamy pozycję
                              ; znalezionego elementu

Przykładowe programy

Uwaga:

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.
Pascal
// Wyszukiwanie liniowe z wartownikiem
// Data:   27.04.2008
// (C)2020 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.
C++
// Wyszukiwanie liniowe z wartownikiem
// Data:   26.04.2008
// (C)2020 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;
}
Basic
' Wyszukiwanie liniowe z wartownikiem
' Data:   27.04.2008
' (C)2020 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 ' Wartownik
  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
Python (dodatek)
# Wyszukiwanie liniowe z wartownikiem
# Data:   21.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

def szukaj(t, n, k, p):
    t.append(k)  # Wstawiamy wartownika
    for i in range(p, n + 1):
        if t[i] == k:
            t.pop() # Usuwamy wartownika
            if i == n:
                return -1
            else:
                return i


t = []
n = int(input())
for i in range(n):
    t.append(int(input()))
k = int(input())
print()
print(szukaj(t, n, k, 0))
print()
t.clear()
Wynik:
5
13
18
954
235
12
235

3
  
5
13
18
954
235
12
119

-1

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.