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

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:

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.

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:

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:

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.

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

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

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