ID: 2694
Algorytmy
Średnie
Źródło: Arkusze CKE
Algorytm wyszukiwania sekwencyjnego z wykorzystaniem wartownika opiera się na założeniu, że
Warianty odpowiedzi
-
A
zbiór danych wejściowych musi być uporządkowany
-
B
zbiór ma zawsze 100 elementów
-
C
na końcu analizowanego zbioru należy dodać wartownika
-
D
szukany element powinien wystąpić wielokrotnie w zbiorze
Wyjaśnienie
W klasycznym wyszukiwaniu liniowym w każdej pętli musisz sprawdzać dwa warunki: czy znaleziono element oraz czy nie wyszło się poza zakres tablicy.
Wartownik to sprytny trik optymalizacyjny. Doklejamy poszukiwaną wartość na sam koniec tablicy. Dzięki temu mamy gwarancję, że pętla zawsze na coś natrafi i nie musimy w każdym kroku pytać programu o długość tablicy.
Gdy pętla się zatrzyma, sprawdzamy tylko, czy znaleźliśmy ten element na jego oryginalnej pozycji, czy dopiero na samym końcu jako doklejonego wartownika.