Wyszukiwanie liniowe/sekwencyjne


Tematy pokrewne
Tablice – wektory
Podstawowe operacje na tablicach
Wyszukiwanie liniowe
Wyszukiwanie liniowe z wartownikiem
Zliczanie wg kryterium
Wyszukiwanie max lub min
Jednoczesne wyszukiwanie max i min
Zastosowania wyszukiwania – sortowanie przez wybór
Wyszukiwanie najczęstszej wartości w zbiorze – dominanta
Wyszukiwanie lidera
Wyszukiwanie binarne
Wyszukiwanie interpolacyjne
Wyszukiwanie k-tego największego elementu
Wyszukiwanie szybkie k-tego największego elementu
Wyszukiwanie mediany zbioru
Zbiory rozłączne – implementacja w tablicy
Sumy prefiksowe
Wbudowane generatory liczb pseudolosowych

 

Problem

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

 

 

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, n N
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. 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 nie znalezienia elementu.

Zmienne pomocnicze
i  –  przebiega przez kolejne indeksy elementów Z. i C
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

 

Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie liniowe
// Data:   26.04.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie liniowe
// Data:   26.04.2008
// (C)2012 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;
}
Free Basic
' Wyszukiwanie liniowe
' Data:   26.04.2008
' (C)2012 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

-1

 

Program

Ważne:

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.

 

Lazarus
// Wyszukiwanie liniowe
// Data:   26.04.2008
// (C)2012 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.
Code::Blocks
// Wyszukiwanie liniowe
// Data:   26.04.2008
// (C)2012 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;
}
Free Basic
' Wyszukiwanie liniowe
' Data:   26.04.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.