Wyszukiwanie liniowe i binarne

Strona ta przedstawia dwa fundamentalne algorytmy wyszukiwania: liniowe i binarne, wraz z ich implementacją w języku Python.

Wyszukiwanie liniowe to prosty algorytm o złożoności czasowej O$n$. Polega on na sekwencyjnym przeglądaniu elementów zbioru w poszukiwaniu elementu spełniającego określony warunek.

Highlight: Wyszukiwanie liniowe Python jest najprostszą metodą wyszukiwania, ale może być nieefektywne dla dużych zbiorów danych.

Implementacja wyszukiwania liniowego w Pythonie wygląda następująco:

def WyszukiwanieLiniowe(lista, x):
    for i in range(len(lista)):
        if lista[i] == x:
            return i

Example: Dla listy [3, 7, 9, 21, 67, 71, 88, 90], wyszukiwanie elementu 9 zwróci indeks 2.

Wyszukiwanie binarne jest bardziej zaawansowanym algorytmem o złożoności czasowej O(log n). Działa on poprzez wielokrotne dzielenie posortowanej listy na połowy, co znacznie przyspiesza proces wyszukiwania.

Highlight: Wyszukiwanie binarne Python jest znacznie efektywniejsze niż wyszukiwanie liniowe dla dużych, posortowanych zbiorów danych.

Implementacja wyszukiwania binarnego w Pythonie:

def WyszukiwanieBinarne(lista, x):
    l = 0  # indeks lewego końca tablicy
    p = len(lista)  # indeks prawego końca tablicy
    while l <= p:
        sr = int((l+p)/2)  # środkowy indeks tablicy
        if lista[sr] == x:
            return sr
        elif lista[sr] > x:
            p = sr - 1
        else:
            l = sr + 1

Example: Dla tej samej listy [3, 7, 9, 21, 67, 71, 88, 90], wyszukiwanie elementu 67 zwróci indeks 4.

Vocabulary: Złożoność czasowa to miara określająca, jak czas wykonania algorytmu rośnie wraz z rozmiarem danych wejściowych.

Oba algorytmy są fundamentalne w nauce programowania i często wykorzystywane w praktyce. Algorytmy w Pythonie takie jak te są kluczowe dla zrozumienia podstaw przetwarzania danych i optymalizacji kodu.