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/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ć 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, n ∈ N.
: 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. p ∈ C.
: poszukiwana wartość, czyli tzw. klucz, wg którego wyszukujemy elementy w Z. Klucz jest tego samego typu co elementy tablicy.

Wyjście:

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

Zmienne pomocnicze:

i : przebiega przez kolejne indeksy elementów Z. i ∈ C.

Lista kroków:

K01: Dla i = p, p + 1, …, n - 1: ; przeglądamy kolejne elementy w zbiorze
     wykonuj K02
K02:   Jeśli Z[i] = k,           ; jeśli napotkamy poszukiwany element, 
       to zakończ z wynikiem i   ; 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
Python (dodatek)
# Wyszukiwanie liniowe
# Data:   21.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

def szukaj(t, n, k, p):
    for i in range(p, n):
        if t[i] == k: return i
    return -1


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

3
  
5
13
18
954
235
12
119

-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 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;
  w := random(10);
  for i := 0 to 99 do
  begin
    Z[i] := random(10);
    L[i] := Z[i] = w;
  end;
  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 <ctime>

using namespace std;

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

  srand(time(NULL));
  w = rand() % 10;
  for(i = 0; i < 100; i++)
  {
    Z[i] = rand() % 10;
    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 <<  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
w = Cint(Rnd * 9)
For i = 0 To 99
  Z(i) = Cint(Rnd * 9)
  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
Python (dodatek)
# Wyszukiwanie liniowe
# Data:   21.02.2024
# (C)2024 mgr Jerzy Wałaszek
# --------------------------

import random

Z = []
L = []
w = random.randrange(10)  # Szukana wartość
for i in range(100):
    Z.append(random.randrange(10))
    L.append(Z[i] == w)
print(w)
print()
c = 0
for i in range(100):
    if L[i]:
        print(f" ->%1d" % Z[i], end="")
    else:
        print(f"   %1d" % Z[i], end="")
    c += 1
    if c == 20:
        print()
        c = 0
print()
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
©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.