Porównanie wyszukiwania liniowego i binarnego

4.1 Porównanie złożoności czasowej wyszukiwania liniowego i binarnego

Porównajmy złożoność czasową wyszukiwania liniowego i binarnego.

Wyszukiwanie liniowe:

• Złożoność czasowa: O(n), gdzie n to liczba elementów w tablicy lub liście.
• Najlepszy przypadek: O(1) — element znaleziony na pierwszym miejscu.
• Przeciętny przypadek: O(n/2) = O(n) — element znaleziony średnio mniej więcej w środku.
• Najgorszy przypadek: O(n) — element znaleziony na ostatnim miejscu lub nieobecny.

Wyszukiwanie binarne:

• Złożoność czasowa: O(log n), gdzie n to liczba elementów w tablicy lub liście.
• Najlepszy przypadek: O(1) — element znaleziony w pierwszym kroku (środkowy element).
• Przeciętny przypadek: O(log n) — wyszukiwanie w posortowanej tablicy.
• Najgorszy przypadek: O(log n) — element znaleziony na ostatnim kroku lub nieobecny.

Przykład analizy złożoności czasowej

Wyszukiwanie liniowe:

• Tablica [1, 3, 5, 7, 9, 11, 13], szukany element 7.
• Sprawdzanie każdego elementu do znalezienia 7 na indeksie 3.
• Zajęło to 4 sprawdzenia, co odpowiada O(n).

Wyszukiwanie binarne:

• Tablica [1, 3, 5, 7, 9, 11, 13], szukany element 7.
• Środkowy element (7) znaleziony w pierwszym kroku.
• Zajęło to 1 sprawdzenie, co odpowiada O(log n).

4.2 Zalety i wady każdego rodzaju wyszukiwania

Omówmy zalety i wady każdego typu wyszukiwania.

Wyszukiwanie liniowe:

Zalety:

• Prostota implementacji: Wyszukiwanie liniowe jest bardzo łatwe do zaimplementowania i zrozumienia.
• Brak wymagań dla danych: Wyszukiwanie liniowe może być używane na nieposortowanych danych.
• Pasuje do małych tablic: Wyszukiwanie liniowe jest efektywne dla małych tablic.

Wady:

• Niska efektywność dla dużych tablic: Złożoność czasowa O(n) czyni go nieefektywnym dla dużych tablic.
• Długi czas działania: Dla dużych tablic wyszukiwanie liniowe może zająć dużo czasu, zwłaszcza jeśli szukany element znajduje się bliżej końca tablicy lub jest nieobecny.

Wyszukiwanie binarne:

Zalety:

• Wysoka efektywność dla dużych tablic: Złożoność czasowa O(log n) czyni go bardzo efektywnym dla dużych tablic.
• Szybkie wykonanie: Wyszukiwanie binarne jest znacznie szybsze niż liniowe przy pracy z dużymi posortowanymi tablicami.

Wady:

• Wymaganie posortowanych danych: Wyszukiwanie binarne działa tylko na posortowanych tablicach, co może wymagać dodatkowego czasu na wstępną sortowanie.
• Złożoność implementacji: Implementacja wyszukiwania binarnego jest bardziej skomplikowana w porównaniu do liniowego.

4.3 Kiedy używać którego wyszukiwania

Rozważmy, kiedy używać wyszukiwania liniowego, a kiedy binarnego.

Wyszukiwanie liniowe.

Użyj wyszukiwania liniowego, gdy:

• Tablica lub lista nie są posortowane.
• Rozmiar tablicy lub listy jest mały.
• Potrzebna jest prostota i szybkie rozwiązanie bez dodatkowych kosztów sortowania.
• Trzeba znaleźć pierwsze wystąpienie lub wszystkie wystąpienia elementu.
• Dane przychodzą w czasie rzeczywistym, a ich wstępne sortowanie jest niemożliwe lub nieopłacalne.

Wyszukiwanie binarne.

Użyj wyszukiwania binarnego, jeśli:

• Tablica lub lista są posortowane.
• Rozmiar tablicy lub listy jest duży.
• Częste wyszukiwanie elementów w tym samym zbiorze danych (można posortować dane raz).
• Ważna jest wysoka szybkość wyszukiwania.
• Dopuszczalne jest poświęcenie czasu na wstępne sortowanie danych.

4.4 Przykłady zadań dla wyszukiwania liniowego

1. Wyszukiwanie w nieposortowanej liście

Trzeba znaleźć indeks danego liczby w nieposortowanej liście liczb.

Przykład:

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

arr = [4, 2, 7, 1, 9, 3]
target = 7
print(linear_search(arr, target))  # Wynik: 2

2. Wyszukiwanie pierwszego wystąpienia w tablicy

Trzeba znaleźć pierwsze wystąpienie danego elementu w liście stringów.

Przykład:

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

words = ["apple", "banana", "cherry", "date", "banana"]
target = "banana"
print(linear_search(words, target))  # Wynik: 1

3. Wyszukiwanie w danych czasu rzeczywistego

Znajdź element w strumieniu danych przychodzących w czasie rzeczywistym.

Przykład:

import random

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

stream = [random.randint(1, 100) for _ in range(100)]
target = 50
print(find_in_stream(stream, target))

4.5 Przykłady zadań dla wyszukiwania binarnego

1. Wyszukiwanie w posortowanej tablicy

Trzeba znaleźć indeks danego liczby w posortowanej tablicy liczb.

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

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
print(binary_search(sorted_array, target))  # Wynik: 3

2. Częste wyszukiwanie w dużym zestawie danych

Często wyszukiwać elementy w dużej posortowanej tablicy liczb.

Przykład:

import random

sorted_large_array = sorted([random.randint(1, 1000000) for _ in range(1000000)])
target = random.choice(sorted_large_array)
print(binary_search(sorted_large_array, target))

3. Wyszukiwanie elementu w posortowanej bazie danych

Znajdź rekord w posortowanej bazie danych po kluczowym polu.

Przykład:

database = sorted([{"id": i, "value": f"record_{i}"} for i in range(100000)])
def binary_search_db(db, target_id):
    left, right = 0, len(db) - 1
    while left <= right:
        mid = (left + right) // 2
        if db[mid]["id"] == target_id:
            return db[mid]
        elif db[mid]["id"] < target_id:
            left = mid + 1
        else:
            right = mid - 1
    return None

target_id = 54321
print(binary_search_db(database, target_id))

1

Опрос

Algorytmy wyszukiwania,  53 уровень,  3 лекция

недоступен

Algorytmy wyszukiwania

Algorytmy wyszukiwania

Открыть