Przykłady zadań dla wyszukiwania liniowego i binarnego

3.1 Zadanie: znajdź element w tablicy za pomocą wyszukiwania liniowego

Zadanie: Dano tablicę liczb. Należy znaleźć indeks określonej liczby za pomocą wyszukiwania liniowego. Jeśli liczba nie zostanie znaleziona, zwracamy -1.

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 = [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óry nie znajduje się 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

Wyjaśnienie:

• Funkcja linear_search przechodzi przez każdy element tablicy arr i porównuje go z target.
• Jeśli element zostanie znaleziony, zwracany jest jego indeks.
• Jeśli wszystkie elementy zostaną sprawdzone, a wartość nie zostanie znaleziona, funkcja zwraca -1.

Kroki wykonania:

1. Tablica [4, 2, 7, 1, 9, 3] i poszukiwana wartość 7.
2. Rozpoczęcie wyszukiwania: pierwszy element (4) porównywany z 7 — brak zgodności.
3. Przejście do następnego elementu (2) — brak zgodności.
4. Przejście do następnego elementu (7) — zgodność.
5. Zwracamy indeks 2.

3.2 Zadanie: znajdź element w posortowanej tablicy za pomocą wyszukiwania binarnego

Zadanie: Dano posortowaną tablicę liczb. Należy znaleźć indeks określonej liczby za pomocą wyszukiwania binarnego. Jeśli liczba nie zostanie znaleziona, zwracamy -1.

Przykład:

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
result = binary_search(sorted_array, target)
print(f"Element {target} znaleziony na indeksie {result}")  # Wyjście: Element 7 znaleziony na indeksie 3

# Przykład użycia dla elementu, który nie znajduje się w tablicy:
target = 6
result = binary_search(sorted_array, target)
print(f"Element {target} znaleziony na indeksie {result}")  # Wyjście: Element 6 znaleziony na indeksie -1

Wyjaśnienie:

• Funkcja binary_search używa dwóch wskaźników (left i right) do śledzenia granic wyszukiwania w tablicy arr.
• Na każdej iteracji znajdowany jest element środkowy tablicy i porównywany z target.
• Jeśli element środkowy jest równy target, zwracany jest jego indeks.
• Jeśli target jest mniejszy od elementu środkowego, wyszukiwanie kontynuowane jest w lewej połowie tablicy.
• Jeśli target jest większy od elementu środkowego, wyszukiwanie kontynuowane jest w prawej połowie tablicy.
• Jeśli granice się przetną i element nie zostanie znaleziony, zwracamy -1.

Kroki wykonania:

1. Posortowana tablica [1, 3, 5, 7, 9, 11, 13] i poszukiwana wartość 7.
2. Początkowe granice wyszukiwania: left = 0, right = 6.
3. Znalezienie elementu środkowego: mid = (0 + 6) // 2 = 3.
4. Porównanie elementu środkowego (7) z target (7) — zgodność.
5. Zwracamy indeks 3.

3.3 Porównanie i wybór odpowiedniego algorytmu wyszukiwania

Porównanie wyszukiwania liniowego i binarnego:

Wybór odpowiedniego algorytmu

Wyszukiwanie liniowe:

• Używane, gdy dane nie są posortowane.
• Odpowiednie dla małych tablic lub list.
• Stosowane, gdy liczba elementów jest niewielka i czas wykonania nie jest istotny.

Wyszukiwanie binarne:

• Stosowane, gdy dane są posortowane.
• Idealne dla dużych tablic, gdzie szybkość wyszukiwania jest kluczowa.
• Efektywne, jeśli często poszukujesz danych w tym samym zbiorze (możesz wcześniej posortować dane).

3.4 Zadania praktyczne na utrwalenie materiału

Zadanie 1: Wyszukiwanie liniowe

Dano tablicę liczb. Napisz funkcję, która znajdzie określoną liczbę za pomocą wyszukiwania liniowego. Funkcja powinna zwrócić indeks znalezionego elementu lub -1, jeśli element nie zostanie znaleziony.

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 = [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

# Dodatkowe testy:
assert linear_search(arr, 9) == 4
assert linear_search(arr, 5) == -1

Zadanie 2: Wyszukiwanie binarne

Dano posortowaną tablicę liczb. Napisz funkcję, która znajdzie określoną liczbę za pomocą wyszukiwania binarnego. Funkcja powinna zwrócić indeks znalezionego elementu lub -1, jeśli element nie zostanie znaleziony.

Przykład:

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
result = binary_search(sorted_array, target)
print(f"Element {target} znaleziony na indeksie {result}")  # Wyjście: Element 7 znaleziony na indeksie 3

# Dodatkowe testy:
assert binary_search(sorted_array, 1) == 0
assert binary_search(sorted_array, 13) == 6
assert binary_search(sorted_array, 6) == -1

Zadanie 3: Porównanie wyszukiwania liniowego i binarnego

Dano tablicę liczb. Napisz dwie funkcje: jedną do wyszukiwania za pomocą wyszukiwania liniowego, a drugą za pomocą wyszukiwania binarnego. Porównaj wydajność obu funkcji na dużych tablicach.

Przykład:

import time
import random

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

# Wyszukiwanie binarne
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

# Generowanie dużej tablicy
large_array = [random.randint(0, 1000000) for _ in range(1000000)]
sorted_large_array = sorted(large_array)
target = random.choice(large_array)

# Porównanie wydajności
start_time = time.time()
linear_search(large_array, target)
print(f"Wyszukiwanie liniowe zajęło: {time.time() - start_time:.6f} sekund")

start_time = time.time()
binary_search(sorted_large_array, target)
print(f"Wyszukiwanie binarne zajęło: {time.time() - start_time:.6f} sekund")