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

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie liniowe/sekwencyjne

SPIS TREŚCI
Tematy pomocnicze

Problem

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

Rozwiązanie

Wyszukiwanie liniowe ( ang. linear search ), zwane również sekwencyjnym ( ang. sequential search ) polega na przeglądaniu kolejnych elementów zbioru Z. Jeśli przeglądany element posiada odpowiednie własności ( np. jest liczbą o poszukiwanej wartości ), to zwracamy jego pozycję w zbiorze i kończymy. W przeciwnym razie kontynuujemy poszukiwania aż do przejrzenia wszystkich pozostałych elementów zbioru Z.

W przypadku pesymistycznym, gdy poszukiwanego elementu nie ma w zbiorze lub też znajduje się on na samym końcu zbioru, algorytm musi wykonać przynajmniej n  obiegów pętli sprawdzającej poszczególne elementy. Wynika z tego, iż pesymistyczna klasa złożoności obliczeniowej jest równa O ( n  ), czyli jest liniowa – stąd pochodzi nazwa metody wyszukującej.

Często chcemy znaleźć wszystkie wystąpienia w zbiorze poszukiwanej wartości elementu. W takim przypadku algorytm na wejściu powinien otrzymywać dodatkowo pozycję ( indeks ) elementu, od którego ma rozpocząć wyszukiwanie. Pozycję tę przy kolejnym przeszukiwaniu podajemy zawsze o 1 większą od ostatnio znalezionej. Dzięki temu nowe poszukiwanie rozpocznie się tuż za poprzednio znalezionym elementem.

Algorytm wyszukiwania liniowego/sekwencyjnego

Wejście:

n  –   liczba elementów w tablicy Z, nN.
Z  – tablica zawierająca elementy do przeszukania. Indeksy elementów rozpoczynają się od 0, a kończą na n - 1.
p  – indeks pierwszego elementu Z, od którego rozpoczniemy poszukiwania. pC.
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. iC.

Lista kroków:

K01: Dla i  = p, p + 1, ..., n - 1:
wykonuj K02
przeglądamy kolejne elementy w zbiorze
K02:     Jeśli Z [ i  ] = k,
    to zakończ z wynikiem i
jeśli napotkamy poszukiwany element, zwracamy jego pozycję
K03: Zakończ z wynikiem -1 jeśli elementu nie ma w tablicy, zwracamy -1

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
// Data:   26.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
  Szukaj := -1;

  for i := p to n - 1 do
    if T [ i ] = k then
    begin
      Szukaj := i; break;
    end
end;

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

begin
  readln ( n );

  SetLength ( Z, n );

  for i := 0 to n - 1 do readln ( Z [ i ] );

  readln ( k );

  writeln;
  writeln ( Szukaj ( Z, n, k, 0 ) );
  writeln;

  SetLength ( Z, 0 );
end.
C++
// Wyszukiwanie liniowe
// 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 )
{
  for( int i = p; i < n; i++ )
    if( T [ i ] == k ) return i;

  return -1;
}

int main( )
{
  int * Z, n, k, i;
  
  cin >> n;

  Z = new int [ n ];

  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
' Data:   26.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
  Szukaj = -1
  For i = p To n - 1
    If T [ i ] = k Then
      Szukaj = i
      Exit For
    End If
  Next
End Function

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

Open Cons For Input As #1

Input #1, n

Z = New Integer [ n ] 

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

Input #1, k

Close #1

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

Delete [ ] Z

End
Wynik:
5
13
18
954
235
12
111

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 wypełnia 100 elementową tablicę Z  całkowitymi liczbami pseudolosowymi z zakresu od 0 do 9. Następnie losuje nową liczbę pseudolosową z tego samego zakresu i znajduje wszystkie jej wystąpienia w Z  przy pomocy wyszukiwania liniowego. Na końcu wyświetla wylosowaną liczbę oraz zawartość Z z zaznaczonymi jej wystąpieniami. Do zapamiętywania wystąpień służy druga tablica L  o elementach logicznych. Jeśli i-ty element tej tablicy zawiera true, to w i-tym elemencie tablicy Z  znajduje się poszukiwany element.
Pascal
// Wyszukiwanie liniowe
// Data:   26.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

program prg;

var
  Z : array [ 0..99 ] of integer;
  L : array [ 0..99 ] of boolean;
  i, w : integer;

begin
  randomize;

  for i := 0 to 99 do Z [ i ] := random ( 10 );

  w := random ( 10 );

  for i := 0 to 99 do L [ i ] := Z [ i ] = w;

  writeln ( w ); writeln;

  for i := 0 to 99 do
  begin
    if L [ i ] then write ( ' ->' )
    else            write ( '   ' );
    write ( Z [ i ] );
  end;

  writeln;
end.
C++
// Wyszukiwanie liniowe
// Data:   26.04.2008
// (C)2020 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

int main( )
{
  int Z [ 100 ], i, w;
  bool L [ 100 ];

  srand ( ( unsigned )time ( NULL ) );

  for( i = 0; i < 100; i++ ) Z [ i ] = rand( ) % 10;

  w = rand( ) % 10;

  for( i = 0; i < 100; i++ ) L [ i ] = ( Z [ i ] == w );

  cout << w << endl << endl;

  for( i = 0; i < 100; i++ )
  {
    if( L [ i ] ) cout << " ->";
    else          cout << "   ";
    cout << Z [ i ];
  }

  cout << endl;
  return 0;
}
Basic
' Wyszukiwanie liniowe
' Data:   26.04.2008
' (C)2020 mgr Jerzy Wałaszek
'---------------------------

Dim As Integer Z ( 99 ), i, w
Dim As Byte L ( 99 )

Randomize

For i = 0 To 99
  Z ( i ) = Cint ( Rnd * 9 )
Next

w = Cint ( Rnd * 9 )

For i = 0 To 99
  L ( i ) = ( Z ( i ) = w )
Next

Print w;
Print

For i = 0 To 99
  If L ( i ) Then
    Print Using " ->#";Z ( i );
  Else
    Print Using "   #";Z ( i );
  End If
Next
Print
End
Wynik:
3

   4   2   2   5   1   2   6   6   4   4   9   6   0   7   8   0   2   5   4   8
   5   2   5 ->3   9   7   6 ->3   1 ->3   6   5   1   7   4   9   5 ->3   7   8
   1   5   7   4   6   2   1   2   4   0   6   1   6   4   7   8   1   4   9   2
   7   0   6   8   7   6   4   1   7   8   4   8 ->3   8   2   8   7   0   7   6
   2   6   0   6   4   0   5   0   8 ->3   2   7   9   0   1   7   5   4   9   9
Wyszukiwanie liniowe
(C)2020 mgr Jerzy Wałaszek


...

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
©2020 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.