Algorytm wyszukiwania liniowego z wartownikiem

Program symuluje działanie algorytmu wyszukiwania liniowego z wartownikiem wartości w zbiorze.

Algorytm wyszukiwania liniowego:

Algorytm wyszukiwania liniowego z wartownikiem jest usprawnieniem tradycyjnego algorytmu wyszukiwania liniowego.

Polega na dodaniu na końcu zbioru (tablicy) tzw. wartownika - czyli elementu równego poszukiwanemu elementowi, dzięki temu mamy pewności, że poszukiwany element na pewno przeszukiwanym zbiorze. W momencie znalezienia wyszukiwanego elementu sprawdzamy czy indeks tego elementu jest mniejszy od liczby elementów w tablicy (licząc z wartownikiem) jeśli tak, to zwracamy index znalezionego elementu, w przeciwnym razie zwracamy -1.

Dzięki zastasowaniu wartownika, nie musimy przy każdej iteracji sprawdzać dodatkowo czy czasem nie osiągneliśmy już końca tablicy - co przyspiesza działanie programu.

Przykładowa implementacje w Pythonie

  1. a = [5, 12, 1, 88, 45, 21, 68, 99, 56, 4]
  2. N = len(a)
  3.  
  4. def znajdz_dana(wartosc):
  5.   a.append(wartosc)
  6.   i = 0;
  7.   while a[i] != wartosc:
  8.       i += 1
  9.   if(i < N): return i
  10.  
  11.   return -1
  12.  
  13. szukana = 45 
  14. pozycja = znajdz_dana(szukana)
  15. if pozycja != -1:
  16.     print(f'Liczbę {szukana} znaleziono na pozycji {pozycja}.')
  17. else:
  18.     print(f'W przeszukiwanej liście nie znaleziono liczby {szukana}.')
  19.