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

  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:

 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

i ← i+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.

 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

i ←  i+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:

 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:

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

 1a

Z[n] ← k

   1

 1b

i ← 0

   1

 2

 3

Jeśli Z[i] = k, 
to idź do 6

  n+1

 4

i ← i+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.

 1a

Z[n] ← k

    1

 1b

i ← 0

    1

  2

  3

Jeśli Z[i] = k, 
to idź do 6

   n/2+1

  4

i ← i+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).:

    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

K01: Z[n] ← k ; na końcu zbioru umieszczamy wartownika
K02: i ← p ; 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 jest 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

// 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.

// 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;
}

' 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 If
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

# 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


n = int(input())
t = [int(input()) for i in range(n)]
k = int(input())
print()
print(szukaj(t, n, k, 0))
print()
t.clear()

5
13
18
954
235
12
235

3

5
13
18
954
235
12
119

-1