Problem jest następujący:
W n elementowym zbiorze wyszukać element o zadanych własnościach. Zadanie przeszukiwania sekwencyjnego polega na przeglądaniu kolejnych elementów zbioru. Znaleziony element zostaje zwrócony (zwykle interesuje nas nie sam element, ale jego pozycja w zbiorze) lub algorytm zwraca informację, iż poszukiwanego elementu w zbiorze nie ma.
Ponieważ wymagane jest sprawdzenie kolejnych elementów zbioru, to w przypadku pesymistycznym (brak poszukiwanego elementu, lub jest on na samym końcu zbioru) algorytm musi wykonać n porównań, gdzie n jest liczbą elementów w zbiorze. Pesymistyczna złożoność czasowa jest następująca:
W(n) = n
Jeśli elementy są rozłożone losowo, to prawdopodobieństwo znalezienia poszukiwanego elementu na każdej pozycji w zbiorze jest takie samo i wynosi:
pi = 1 , i = 1,2,...,n n Oczekiwana złożoność czasowa algorytmu jest równa:
W obu przypadkach klasa czasowej złożoności obliczeniowej jest liniowa i wynosi O(n). Dokładniejszy opis czasowych złożoności obliczeniowych oraz notacji omikron znajdziesz w artykułach o algorytmach sortujących oraz o liczbach pierwszych.
Dane wejściowe
n - liczba elementów w zbiorze wejściowym, i N
d[ ] - zbiór wejściowy, w którym dokonujemy poszukiwań. Indeksy elementów rozpoczynają się od 1. x - wartość poszukiwana Dane wyjściowe
p - pozycja elementu x w zbiorze d[ ]. Jeśli p = 0, to element x w zbiorze nie występuje. p
krok 1: p 1
krok 2: Dopóki (p n)
(x
d[p]) wykonuj p
krok 3: Jeśli p > n, to p krok 4: Zakończ algorytm
Przeszukiwanie zbioru rozpoczynamy od pierwszego elementu. Zmienna p przechowuje pozycję sprawdzanego elementu i na początku przyjmuje wartość 1.
W pętli warunkowej najpierw sprawdzamy, czy pozycja p wskazuje element wewnątrz zbioru. Jeśli nie, pętla jest przerywana.
Drugi test w pętli sprawdza, czy element zbioru leżący na pozycji p jest różny od poszukiwanego elementu x. Jeśli tak, to pozycja p jest zwiększana o 1 wskazując kolejny element zbioru i pętla kontynuuje się. Jeśli nie, to element został znaleziony i pętla zostaje przerwana.
Wyjście z pętli przeszukującej zbiór następuje w dwóch przypadkach:
- przeglądnięty został cały zbiór, elementu x nie znaleziono i pozycja p jest większa od n.
- znaleziono element x w zbiorze na pozycji p.
Zatem w przypadku gdy p > n, elementu x nie znaleziono i zerujemy pozycję p, aby zgłosić ten fakt. Inaczej p zawiera pozycję w zbiorze, na której znajduje się poszukiwany przez nas element x.
Ostatni test właściwie nie jest konieczny - program wykorzystujący ten algorytm może przecież sprawdzić, czy p jest większe od n. Jednakże wyzerowanie p jest bardziej czytelne i intuicyjne - w zbiorze nie ma elementu na pozycji zero. Zwracanie zera w przypadku niepowodzenia jest często stosowaną praktyką w programowaniu (jeśli zero jest możliwą wartością, to często zwraca się minus jeden dla zaznaczenia porażki)..
Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.
Program tworzy zbiór 100 liczb pseudolosowych z zakresu od 0 do 99. Następnie generuje wartość pseudolosową z zakresu od 0 do 99 i szuka jej w zbiorze. Jeśli znajdzie, zaznacza element zbioru i podaje jego pozycję. Jeśli nie znajdzie, wypisuje odpowiedni komunikat.
| Efekt uruchomienia programu |
|---|
Przeszukiwanie sekwencyjne |
Przeszukiwanie sekwencyjne |
// Przeszukiwanie sekwencyjne
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------
program seqsearch;
{$APPTYPE CONSOLE}
const
N = 100; // liczba elementów w zbiorze
M = 99; // maksymalna wartość elementów
// Deklaracja zmiennych
var
d : array[1..N] of cardinal;
i,p,x : cardinal;
begin
writeln('Przeszukiwanie sekwencyjne');
writeln('--------------------------');
writeln('(C)2006 mgr Jerzy Walaszek');
writeln(' I LO w Tarnowie ');
writeln;
// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
randomize;
for i := 1 to N do d[i] := random(M + 1);
// Generujemy poszukiwaną wartość
x := random(M + 1);
// Szukamy x w d[ ]
p := 1;
while (p <= N) and (x <> d[p]) do inc(p);
if p > N then p := 0;
// Prezentujemy wyniki
for i := 1 to N do
if i = p then write('>',d[i]:2,'<') else write(d[i]:3,' ');
writeln;
write('x = ',x);
if p > 0 then
writeln(' wystepuje na pozycji nr ',p)
else
writeln(' nie wystepuje w zbiorze.');
writeln;
// Gotowe
write('KONIEC. Nacisnij klawisz Enter...'); readln;
end.
// Przeszukiwanie sekwencyjne
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------
#include <iostream>
#include <iomanip>
using namespace std;
int main(void)
{
const int N = 100; // liczba elementów w zbiorze
const int M = 99; // maksymalna wartość elementów
// Deklaracja zmiennych
unsigned d[N + 1],i,p,x;
cout << "Przeszukiwanie sekwencyjne\n"
"--------------------------\n"
"(C)2006 mgr Jerzy Walaszek\n"
" I LO w Tarnowie \n\n";
// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
srand((unsigned)time(NULL));
for(i = 1; i <= N; i++) d[i] = rand() % (M + 1);
// Generujemy poszukiwaną wartość
x = rand() % (M + 1);
// Szukamy x w d[ ]
p = 1;
while((p <= N) && (x != d[p])) p++;
if(p > N) p = 0;
// Prezentujemy wyniki
for(i = 1; i <= N; i++)
if(i == p)
cout << ">" << setw(2) << d[i] << "<";
else
cout << setw(3) << d[i] << " ";
cout << "\nx = " << x;
if(p)
cout << " wystepuje na pozycji nr " << p << endl << endl;
else
cout << " nie wystepuje w zbiorze.\n\n";
// Gotowe
system("pause"); return 0;
}
' Przeszukiwanie sekwencyjne
'-------------------------------------------
' (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
'-------------------------------------------
Module Module1
Sub Main()
Const N = 100 ' liczba elementów w zbiorze
Const M = 99 ' maksymalna wartość elementów
' Deklaracja zmiennych
Dim d(N), i, p, x As Integer
Console.WriteLine("Przeszukiwanie sekwencyjne")
Console.WriteLine("--------------------------")
Console.WriteLine("(C)2006 mgr Jerzy Wałaszek")
Console.WriteLine(" I LO w Tarnowie ")
Console.WriteLine()
' Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
Randomize()
For i = 1 To N : d(i) = Int(Rnd(1) * (M + 1)) : Next
' Generujemy poszukiwaną wartość
x = Int(Rnd(1) * (M + 1))
' Szukamy x w d[ ]
p = 1
While (p <= N) AndAlso (x <> d(p)) : p += 1 : End While
If p > N Then p = 0
' Prezentujemy wyniki
For i = 1 To N
If i = p Then
Console.Write(">{0,2}<", d(i))
Else
Console.Write(" {0,2} ", d(i))
End If
Next
Console.WriteLine()
Console.Write("x = {0}", x)
If p > 0 Then
Console.WriteLine(" występuje na pozycji nr {0}", p)
Else
Console.WriteLine(" nie występuje w zbiorze.")
End If
Console.WriteLine()
' Gotowe
Console.WriteLine("KONIEC. Naciśnij dowolny klawisz...")
Console.ReadLine()
End Sub
End Module
# -*- coding: cp1250 -*-
# Przeszukiwanie sekwencyjne
#-------------------------------------------
# (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
#-------------------------------------------
import random
N = 100 # liczba elementów w zbiorze
M = 99 # maksymalna wartość elementów
d = []
print "Przeszukiwanie sekwencyjne"
print "--------------------------"
print "(C)2006 mgr Jerzy Wałaszek"
print " I LO w Tarnowie "
# Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
for i in range(N): d.append(random.randint(0, M))
# Generujemy poszukiwaną wartość
x = random.randint(0, M)
# Szukamy x w d[ ]
p = 0
while (p < N) and (x != d[p]): p += 1
if p == N: p = -1
# Prezentujemy wyniki
for i in range(N):
if i == p:
print ">%2d<" % d[i],
else:
print " %2d " % d[i],
print "x =", x,
if p >= 0:
print "występuje na pozycji nr", p + 1
else:
print "nie występuje w zbiorze."
# Gotowe
raw_input("KONIEC. Naciśnij klawisz Enter...")
<html>
<head>
</head>
<body>
<div align="center">
<form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px;
BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px;
PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset;
PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset;
BACKGROUND-COLOR: #ffcc66" name="frmseqsearch">
<h4 style="TEXT-ALIGN: center">Przeszukiwanie sekwencyjne</h4>
<p style="TEXT-ALIGN: center">
(C)2006 mgr Jerzy Wałaszek<br>
I LO w Tarnowie
</p>
<hr>
<p style="TEXT-ALIGN: center">
<input type="button" value="Szukaj" name="B1" onclick="main();">
</p>
<p style="TEXT-ALIGN: center" id="t_out">...</p>
</form>
<script language=javascript>
// Przeszukiwanie sekwencyjne
//-------------------------------------------
// (C)2006 mgr Jerzy Wałaszek I LO w Tarnowie
//-------------------------------------------
function main()
{
var N = 100; // liczba elementów w zbiorze
var M = 99; // maksymalna wartość elementów
// Deklaracja zmiennych
var d = new Array(N + 1);
var i,p,x,t;
// Generujemy zbiór danych, w którym będzie wykonywane poszukiwanie
for(i = 1; i <= N; i++) d[i] = Math.floor(Math.random() * (M + 1));
// Generujemy poszukiwaną wartość
x = Math.floor(Math.random() * (M + 1));
// Szukamy x w d[ ]
p = 1;
while((p <= N) && (x != d[p])) p++;
if(p > N) p = 0;
// Prezentujemy wyniki
t = "";
for(i = 1; i <= N; i++)
if(i == p)
t += "<nobr><font color=red><b>>" + d[i] + "<</b></font></nobr>";
else
t += " " + d[i] + " ";
t += "<BR><BR>x = " + x + " ";
if(p)
t += "występuje na pozycji nr " + p;
else
t += "nie występuje w zbiorze.";
// Gotowe
document.getElementById("t_out").innerHTML = t;
}
</script>
</div>
</body>
</html>
GNU Free Documentation License.
Źródło: mgr Jerzy Wałaszek