Zadania algorytmiczne dotyczące wyszukiwania

9.1 Przykłady zadań rozwiązywanych za pomocą wyszukiwania liniowego i binarnego

Wyszukiwanie liniowe

Zadanie: Wyszukiwanie elementu w tablicy: Dana jest tablica liczb i wartość docelowa. Trzeba znaleźć indeks wartości docelowej w tablicy.

Rozwiązanie: Używamy wyszukiwania liniowego do sprawdzenia każdego elementu tablicy.

Przykład implementacji:

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

# Przykład użycia:
arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # Wyjście: 2

Wyszukiwanie binarne

Zadanie: Wyszukiwanie elementu w posortowanej tablicy: Dana jest posortowana tablica liczb i wartość docelowa. Trzeba znaleźć indeks wartości docelowej w tablicy.

Rozwiązanie: Używamy wyszukiwania binarnego do dzielenia tablicy na połowy i szukania wartości docelowej.

Przykład implementacji:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Przykład użycia:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # Wyjście: 3

9.2 Zadania dotyczące użycia tabel haszujących do optymalizacji wyszukiwania

1. Wyszukiwanie duplikatów w tablicy

Zadanie: Dana jest tablica liczb. Trzeba znaleźć i zwrócić wszystkie duplikaty w tablicy.

Rozwiązanie: Używamy tabeli haszującej do śledzenia liczb, które już się pojawiły. Jeśli liczba pojawia się ponownie, dodajemy ją do listy duplikatów.

Przykład implementacji:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Przykład użycia
arr = [1, 2, 3, 2, 4, 5, 6, 4, 7]
print(find_duplicates(arr))  # Wyjście: [2, 4]

2. Znajdowanie par z daną sumą

Zadanie: Dana jest tablica liczb i wartość docelowa sumy. Trzeba znaleźć wszystkie pary liczb, które sumują się do wartości docelowej.

Rozwiązanie: Używamy tabeli haszującej do przechowywania liczb i sprawdzania, czy tworzą one parę z bieżącą liczbą, która daje wartość docelową sumy.

Przykład implementacji:

def find_pairs_with_sum(arr, target_sum):
    seen = set()
    pairs = []

    for num in arr:
        complement = target_sum - num
        if complement in seen:
            pairs.append((complement, num))
        seen.add(num)

    return pairs

# Przykład użycia
arr = [1, 5, 7, -1, 5]
target_sum = 6
print(find_pairs_with_sum(arr, target_sum))  # Wyjście: [(1, 5), (7, -1), (1, 5)]

9.3 Kombinowane użycie różnych metod wyszukiwania

W skomplikowanych zadaniach często konieczne jest użycie kilku metod wyszukiwania, aby osiągnąć jak najlepszą efektywność. Kombinowane użycie wyszukiwania liniowego, binarnego i tabel haszujących pozwala na bardziej efektywne i elastyczne rozwiązywanie problemów.

Przykład 1: Wyszukiwanie elementu w tablicy i sprawdzanie jego istnienia w innej tablicy

Dane są dwie tablice liczb. Trzeba znaleźć elementy pierwszej tablicy, które istnieją w drugiej tablicy.

Rozwiązanie:

• Używamy tabeli haszującej do przechowywania elementów drugiej tablicy.
• Dla każdego elementu pierwszej tablicy sprawdzamy jego istnienie w tabeli haszującej.

Przykład implementacji:

def find_common_elements(arr1, arr2):
    hash_table = set(arr2)  # Tabela haszująca dla drugiej tablicy
    common_elements = []

    for element in arr1:
        if element in hash_table:
            common_elements.append(element)

    return common_elements

# Przykład użycia:
arr1 = [1, 2, 3, 4, 5]
arr2 = [3, 4, 5, 6, 7]
print(find_common_elements(arr1, arr2))  # Wyjście: [3, 4, 5]

Przykład 2: Sprawdzanie, czy podtablica jest anagramem wzorca z użyciem tabeli haszującej

Dany jest ciąg znaków i wzorzec. Trzeba sprawdzić, czy jakakolwiek podciąg ciągu znaków jest anagramem wzorca.

Rozwiązanie:

• Używamy tabeli haszującej do zliczania częstości znaków we wzorcu.
• Przechodzimy przez tablicę znaków, używając „przesuwającego się okna” do sprawdzania każdej podciągu pod względem zgodności z częstością znaków.

Przykład implementacji:

from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def find_anagram_substring(arr, pattern):
    pattern_length = len(pattern)
    pattern_count = Counter(pattern)
    
    for i in range(len(arr) - pattern_length + 1):
        substring = arr[i:i + pattern_length]
        if is_anagram(substring, pattern):
            return True
    return False

# Przykład użycia:
arr = "cbabadcbbabbcbabaabccbabc"
pattern = "abbc"
print(find_anagram_substring(arr, pattern))  # Wyjście: True

9.4 Zadania praktyczne do utrwalenia materiału

Zadanie 1: Wyszukiwanie elementu w nieposortowanej tablicy

Dana jest tablica liczb i wartość docelowa. Trzeba znaleźć indeks wartości docelowej w tablicy. Użyj wyszukiwania liniowego.

Przykład:

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

# Przykład użycia:
arr = [10, 20, 30, 40, 50]
target = 30
print(linear_search(arr, target))  # Wyjście: 2

Zadanie 2: Wyszukiwanie duplikatów w tablicy

Dana jest tablica liczb. Znajdź i zwróć wszystkie duplikaty w tablicy używając tabeli haszującej.

Przykład:

def find_duplicates(arr):
    seen = set()
    duplicates = []
    for item in arr:
        if item in seen:
            duplicates.append(item)
        else:
            seen.add(item)
    return duplicates

# Przykład użycia:
arr = [1, 3, 5, 3, 7, 9, 1]
print(find_duplicates(arr))  # Wyjście: [3, 1]