Wyszukiwanie liniowe

1.1 Definicja wyszukiwania liniowego

Wyszukiwanie liniowe (znane również jako wyszukiwanie sekwencyjne) to algorytm wyszukiwania elementu w liście lub tablicy, który kolejno sprawdza każdy element, aż znajdzie pasujący lub przeanalizuje wszystkie elementy. To najprostszy algorytm wyszukiwania, który nie wymaga wstępnego sortowania danych.

Główne zasady:

• Sekwencyjne sprawdzanie: Algorytm przechodzi przez każdy element tablicy lub listy, porównując go z poszukiwaną wartością.
• Zakończenie wyszukiwania: Wyszukiwanie kończy się, gdy zostanie znaleziony element zgodny z poszukiwaną wartością lub gdy wszystkie elementy zostaną sprawdzone.
• Nie wymaga sortowania: Wyszukiwanie liniowe może być stosowane do niesortowanych danych.
• Zastosowanie: Wyszukiwanie liniowe może być stosowane do dowolnych struktur danych, które wspierają iterację, w tym listy i tablice.

Wyszukiwanie liniowe ma złożoność czasową O(n), gdzie n to liczba elementów w tablicy lub liście. W najgorszym przypadku algorytm będzie musiał sprawdzić wszystkie n elementów, aby znaleźć poszukiwaną wartość lub określić jej brak.

Analiza złożoności czasowej:

• Najlepszy przypadek (Best case): Element znaleziony na pierwszym miejscu, O(1).
• Przeciętny przypadek (Average case): Element znaleziony gdzieś w środku, O(n/2), co jest równoznaczne z O(n).
• Najgorszy przypadek (Worst case): Element znaleziony na ostatnim miejscu lub nieobecny, O(n).

1.2 Kroki implementacji wyszukiwania liniowego

Kroki wyszukiwania liniowego:

• Inicjalizacja: Ustawić początkowy indeks do wyszukiwania (zwykle indeks zero).
• Sekwencyjne sprawdzanie: Sprawdzać każdy element listy lub tablicy pod kątem zgodności z poszukiwaną wartością.
• Warunek zakończenia: Jeśli element zostanie znaleziony, zwrócić jego indeks. Jeśli wszystkie elementy zostaną sprawdzone, a poszukiwana wartość nie zostanie znaleziona, zwrócić specjalną wartość (zwykle -1 lub None).

Implementacja wyszukiwania liniowego w Pythonie:

def linear_search(arr, target):
    # Przechodzimy przez każdy element tablicy
    for index, element in enumerate(arr):
        # Jeśli obecny element jest równy poszukiwanej wartości, zwracamy jego indeks
        if element == target:
            return index
    # Jeśli element nie zostanie znaleziony, zwracamy -1
    return -1

Krok po kroku wyjaśnienie implementacji:

• Inicjalizacja pętli: Używany jest pętla for z funkcją enumerate, która zwraca indeks i element tablicy przy każdej iteracji.
• Porównanie: Przy każdej iteracji bieżący element jest porównywany z poszukiwaną wartością (target).
• Zwrócenie indeksu: Jeśli bieżący element jest równy poszukiwanej wartości, zwracany jest indeks tego elementu.
• Zwrócenie -1: Jeśli pętla zakończy się, a poszukiwany element nie został znaleziony, zwracane jest -1.

# Przykład użycia:
arr = [4, 2, 7, 1, 9, 3]
target = 7
result = linear_search(arr, target)
print(f"Element {target} znaleziony na indeksie {result}")  # Wyjście: Element 7 znaleziony na indeksie 2

# Przykład użycia dla elementu, którego nie ma w tablicy:
target = 5
result = linear_search(arr, target)
print(f"Element {target} znaleziony na indeksie {result}")  # Wyjście: Element 5 znaleziony na indeksie -1

1.3 Przykłady zadań rozwiązywanych za pomocą wyszukiwania liniowego

Wyszukiwanie liniowe jest używane do rozwiązywania wielu zadań związanych z wyszukiwaniem elementów w kolekcjach danych. Oto kilka przykładów takich zadań:

Zadanie 1: Wyszukiwanie elementu w tablicy

Trzeba znaleźć podaną liczbę w tablicy liczb.

Przykład:

def linear_search(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [10, 23, 45, 70, 11, 15]
target = 70
index = linear_search(arr, target)
print(f"Element {target} znaleziony na indeksie {index}")  # Wyjście: Element 70 znaleziony na indeksie 3

Zadanie 2: Sprawdzenie obecności elementu na liście

Trzeba sprawdzić, czy podana wartość jest obecna na liście ciągów znaków.

Przykład:

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

words = ["apple", "banana", "cherry", "date"]
target = "cherry"
found = linear_search(words, target)
print(f"Element {target} {'znaleziony' if found else 'nie znaleziony'}")  # Wyjście: Element cherry znaleziony

Zadanie 3: Wyszukiwanie minimalnego lub maksymalnego elementu

Trzeba znaleźć minimalną lub maksymalną wartość na liście.

Przykład:

def find_min(arr):
    if not arr:
        return None
    min_val = arr[0]
    for element in arr:
        if element < min_val:
            min_val = element
    return min_val

arr = [34, 17, 23, 2, 45, 13]
min_value = find_min(arr)
print(f"Minimalna wartość: {min_value}")  # Wyjście: Minimalna wartość: 2

Zadanie 4: Wyszukiwanie pierwszego wystąpienia

Znaleźć pierwsze wystąpienie podanego elementu na liście.

Przykład:

def find_first_occurrence(arr, target):
    for index, element in enumerate(arr):
        if element == target:
            return index
    return -1

arr = [4, 2, 7, 1, 9, 3, 2]
target = 2
index = find_first_occurrence(arr, target)
print(f"Pierwsze wystąpienie {target} na indeksie {index}")  # Wyjście: Pierwsze wystąpienie 2 na indeksie 1

Zadanie 5: Liczenie liczby wystąpień

Zliczyć liczbę wystąpień podanego elementu na liście.

Przykład:

def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

arr = [4, 2, 7, 2, 9, 3, 2]
target = 2
count = count_occurrences(arr, target)
print(f"Element {target} występuje {count} razy")  # Wyjście: Element 2 występuje 3 razy