Linear Search with Sentinel Quiz

Algorytmy i struktury danych - Szukanie liniowe z wartownikiem

• Problem: Sprawdzenie, czy liczba y występuje w ciągu n liczb x1, x2, …, xn.

• Specyfikacja:

  • Warunek początkowy:
    • Dane: liczba y, liczba naturalna n (elementy x1, x2, …, xn).
  • Warunek końcowy:
    • Wynik: indeks i elementu, dla którego wartość y = xi, lub 0, jeśli y nie występuje.

Schemat działania algorytmu

• Ustaw: ostatni = xn, xn = y, i = 1.
• Pętla: dopóki y ≠ xi wykonaj i = i + 1, xn = ostatni.
• Warunki zakończenia:
  • Jeśli i < n lub xn = y, zwróć i.
  • W przeciwnym razie zwróć 0.

Przykład zastosowania

• Przykład 1:

  • y = 6, n = 3, x1 = 56, x2 = 12, x3 = 5.
  • Następujące przypisania: ostatni = xn, xn = y, i = 1.
  • W iteracjach:
    • i = 1: 6 ≠ 56
    • i = 2: 6 ≠ 12
    • i = 3: 6 = 6 (x3 = 5)
  • Uwagi: i = 3, zapewnia, że x3 ≠ y, więc wynik to 0.

• Przykład 2:

  • y = 5, n = 3, x1 = 56, x2 = 12, x3 = 5.
  • Z podobnym przebiegiem, algorytm przeszukuje wartości i ocenia indeksy, dopóki nie znajdzie y lub nie zakończy z n.

Test your knowledge of linear search with sentinel in algorithms and data structures. This quiz covers the problem of checking if a given number y exists in a sequence of n numbers x1, x2, ..., xn, and returning the index of the element where the value of y is equal to xi, or 0 if such a value is not found in the sequence.