Algorytmy i Struktury Danych - Wyszukiwanie liniowe

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.
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. Klucz jest tego samego typu co elementy tablicy.

Wyjście:

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

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


n = int(input())
z = [int(input()) for i in range(n)]
k = int(input())
print()
print(szukaj(z, n, k, 0))
print()
z = None

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

JavaScript

<html>
  <head>
    <title>
      Wyszukiwanie
    </title>
  </head>
  <body>

<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>
          Wyszukiwanie liniowe
          </b><br/>
          &nbsp;&nbsp;(C)2026 mgr
          Jerzy Wałaszek
          &nbsp;&nbsp;
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// Wyszukiwanie liniowe
// Data:   26.04.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------

function main()
{
  let Z,i,w,L,c,t;
  Z = Array(100);
  L = Array(100);
  for(i = 0; i < 100; i++)
    Z[i] = Math.floor(
           Math.random() * 10);
  w = Math.floor(
      Math.random() * 10);
  for(i = 0; i < 100; i++)
    L[i] = (Z[i] == w);
  t = w +
      "<br/><br/>" +
      "<table class='small'><tr>";
  c = 0;
  for(i = 0; i < 100; i++)
  {
    t += "<td nowrap><pre>";
    if(L[i]) t += ">";
    else     t += " ";
    t += Z[i]+"</pre></td>";
    c++;
    if(c == 10)
    {
      c = 0;
      t += "</tr>";
      if(i < 99) t += "<tr>";
    }
  }
  t += "</table>";
  document.getElementById("out")
  .innerHTML = t;
}

</script>

  </body>
</html>

do podrozdziału do strony

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.

Wyszukiwanie liniowe/sekwencyjne

Problem

Rozwiązanie

Algorytm wyszukiwania liniowego/sekwencyjnego

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Przykładowe programy