Wyszukiwanie liniowe i binarne w Pythonie i C++

Szukanie elementu w zbiorze danych to jedno z najczęstszych zadań w programowaniu: czy liczba jest na liście, na której pozycji stoi, ile razy występuje, która wartość jest najmniejsza. Są dwa podstawowe sposoby. Wyszukiwanie liniowe sprawdza elementy po kolei i działa zawsze. Wyszukiwanie binarne (ang. binary search, po polsku też wyszukiwanie połówkowe) działa tylko na danych posortowanych, ale jest nieporównanie szybsze.

Na tej stronie znajdziesz oba algorytmy, szukanie minimum i maksimum w jednym przejściu, tabelę przebiegu wyszukiwania binarnego i kod w Pythonie oraz C++. Każdy przykład przejdziesz krok po kroku w kursie Algorytmy z podstawy programowej: w przeglądarce, bez instalowania niczego i bez konta, z podglądem zmiennych w każdym kroku.

Przejdź wyszukiwanie binarne krok po kroku

Wyszukiwanie liniowe: po kolei

Najprostsza metoda: bierzemy pierwszy element, porównujemy z szukanym, potem drugi, trzeci i tak dalej. Gdy trafimy, zwracamy indeks. Gdy dojdziemy do końca listy, elementu nie ma, a funkcja zwraca umowną wartość -1.

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


dane = [7, 3, 9, 4, 12, 5]
print(szukaj(dane, 4))
print(szukaj(dane, 8))

3
-1

Liczba 4 stoi na pozycji 3 (indeksy liczymy od zera), a 8 na liście nie ma. Lista nie musi być posortowana. Ceną jest czas: w najgorszym razie (elementu brak albo stoi na końcu) sprawdzamy wszystkie n elementów. Dla 6 liczb to nic, dla miliona rekordów już sporo.

Ten sam schemat “przejdź po kolei i coś sprawdź” liczy wystąpienia elementu: zamiast kończyć przy pierwszym trafieniu, zwiększamy licznik.

dane = [3, 1, 3, 7, 3, 2, 8, 3]
ile = 0
for x in dane:
    if x == 3:
        ile += 1
print(ile)

4

Krokuj wyszukiwanie liniowe

Minimum i maksimum w jednym przejściu

Bliskim krewnym wyszukiwania liniowego jest szukanie najmniejszego i największego elementu. Zakładamy, że pierwszy element jest jednocześnie najmniejszy i największy, a potem poprawiamy oba wyniki przy każdym lepszym kandydacie:

dane = [7, 3, 9, 4, 12, 5]
najmniejszy = dane[0]
najwiekszy = dane[0]
for x in dane:
    if x < najmniejszy:
        najmniejszy = x
    if x > najwiekszy:
        najwiekszy = x
print(najmniejszy, najwiekszy)

3 12

Tak samo działają wbudowane min() i max(). Ważne, żeby startować od pierwszego elementu listy, a nie od zera: dla listy samych liczb ujemnych start od 0 dałby błędne maksimum 0. Szukanie minimum to też serce sortowania przez wybieranie.

Krokuj minimum i maksimum

Wyszukiwanie binarne w Pythonie

Gdy lista jest posortowana rosnąco, możemy szukać jak w słowniku papierowym. Otwieramy w połowie: jeśli szukane słowo jest dalej w alfabecie, odrzucamy całą lewą połowę, jeśli wcześniej, prawą. Pamiętamy tylko granice przedziału, w którym element jeszcze może być: lewy i prawy.

dane = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
x = 23
lewy = 0
prawy = len(dane) - 1
while lewy <= prawy:
    srodek = (lewy + prawy) // 2
    print(lewy, prawy, "srodek:", dane[srodek])
    if dane[srodek] == x:
        print("znaleziono na pozycji", srodek)
        break
    elif dane[srodek] < x:
        lewy = srodek + 1
    else:
        prawy = srodek - 1
else:
    print("brak")

0 9 srodek: 16
5 9 srodek: 56
5 6 srodek: 23
znaleziono na pozycji 5

Prześledźmy wartości zmiennych:

Trzy sprawdzenia zamiast sześciu, których potrzebowałoby wyszukiwanie liniowe. Różnica rośnie szybko: każde porównanie zmniejsza przedział o połowę, więc dla 1000 elementów wystarczy najwyżej 10 sprawdzeń, a dla miliona około 20. Liczba kroków rośnie jak logarytm o podstawie 2 z liczby elementów. To klasyczny przykład metody dziel i zwyciężaj, którą poznaje się w liceum.

Gdy elementu nie ma, przedział w końcu staje się pusty (lewy > prawy), pętla kończy się bez break i wykonuje się gałąź else pętli while.

Wyszukiwanie binarne jako funkcja z licznikiem kroków

W zadaniach często chodzi nie tylko o pozycję, ale też o to, ile razy trzeba było sprawdzić środek. Funkcja może zwrócić oba wyniki naraz:

def binarne(lista, x):
    lewy = 0
    prawy = len(lista) - 1
    kroki = 0
    while lewy <= prawy:
        srodek = (lewy + prawy) // 2
        kroki += 1
        if lista[srodek] == x:
            return srodek, kroki
        if lista[srodek] < x:
            lewy = srodek + 1
        else:
            prawy = srodek - 1
    return -1, kroki


liczby = list(range(0, 1000, 2))
print(binarne(liczby, 500))
print(binarne(liczby, 2))
print(binarne(liczby, 501))

(250, 8)
(1, 9)
(-1, 9)

Lista ma 500 liczb parzystych, a żadne wyszukiwanie nie potrzebuje więcej niż 9 sprawdzeń. Liniowe szukanie liczby 501 obejrzałoby wszystkie 500 elementów.

Ćwicz: wyszukiwanie binarne z liczeniem kroków

Wyszukiwanie binarne w C++

W C++ dane trzymamy w zwykłej tablicy i przekazujemy jej rozmiar do funkcji. Logika jest identyczna:

#include <iostream>
using namespace std;

int binarne(int t[], int n, int x) {
  int lewy = 0;
  int prawy = n - 1;
  while (lewy <= prawy) {
    int srodek = (lewy + prawy) / 2;
    if (t[srodek] == x) {
      return srodek;
    }
    if (t[srodek] < x) {
      lewy = srodek + 1;
    } else {
      prawy = srodek - 1;
    }
  }
  return -1;
}

int main() {
  int dane[10] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
  cout << binarne(dane, 10, 23) << endl;
  cout << binarne(dane, 10, 91) << endl;
  cout << binarne(dane, 10, 40) << endl;
  return 0;
}

5
9
-1

Dzielenie / dwóch liczb typu int w C++ jest całkowite, więc (lewy + prawy) / 2 działa jak // w Pythonie. Wyszukiwanie liniowe razem z minimum i maksimum w C++ wygląda tak:

#include <iostream>
using namespace std;

int main() {
  int dane[6] = {7, 3, 9, 4, 12, 5};
  int x = 4;
  int pozycja = -1;
  for (int i = 0; i < 6; i++) {
    if (dane[i] == x) {
      pozycja = i;
      break;
    }
  }
  int najmniejszy = dane[0];
  int najwiekszy = dane[0];
  for (int i = 1; i < 6; i++) {
    if (dane[i] < najmniejszy) {
      najmniejszy = dane[i];
    }
    if (dane[i] > najwiekszy) {
      najwiekszy = dane[i];
    }
  }
  cout << "pozycja " << x << ": " << pozycja << endl;
  cout << "min " << najmniejszy << ", max " << najwiekszy << endl;
  return 0;
}

pozycja 4: 3
min 3, max 12

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Wyszukiwanie liniowe

Specyfikacja. Dane: tablica T[1..n] i szukana wartość x. Wynik: pozycja pierwszego elementu równego x albo brak.

Lista kroków:

1. Wczytaj n, tablicę T[1..n] i szukaną x. Ustaw i = 1.
2. Jeśli i > n, wypisz brak i zakończ.
3. Jeśli T[i] = x, wypisz i i zakończ.
4. Zwiększ i o 1 i wróć do kroku 2.

Pseudokod:

wczytaj n, T, x
i ← 1
dopóki i ≤ n i T[i] ≠ x wykonuj
  i ← i + 1
jeżeli i ≤ n to
  wypisz i
w przeciwnym razie
  wypisz "brak"

Schemat blokowy:

Wyszukiwanie binarne

Specyfikacja. Dane: tablica T[1..n] posortowana rosnąco i szukana wartość x. Wynik: pozycja elementu równego x albo brak.

Lista kroków:

1. Wczytaj n, posortowaną rosnąco tablicę T[1..n] i szukaną x. Ustaw l = 1 i p = n (granice przedziału).
2. Jeśli l > p, wypisz brak i zakończ.
3. Oblicz środek przedziału s = (l + p) div 2.
4. Jeśli T[s] = x, wypisz s i zakończ.
5. Jeśli T[s] < x, ustaw l = s + 1, w przeciwnym razie ustaw p = s - 1. Wróć do kroku 2.

Pseudokod:

wczytaj n, T, x
l ← 1
p ← n
w ← 0
dopóki l ≤ p i w = 0 wykonuj
  s ← (l + p) div 2
  jeżeli T[s] = x to
    w ← s
  w przeciwnym razie
    jeżeli T[s] < x to
      l ← s + 1
    w przeciwnym razie
      p ← s - 1
jeżeli w > 0 to
  wypisz w
w przeciwnym razie
  wypisz "brak"

Schemat blokowy:

Drzewo decyzyjne wyszukiwania binarnego. Drzewo pokazuje wszystkie możliwe przebiegi wyszukiwania binarnego w tablicy T = [10, 20, 30, 40, 50, 60, 70]. Każdy węzeł to porównanie szukanej x z elementem środkowym przedziału, a liść to wynik: pozycja x albo brak. Żadna ścieżka nie ma więcej niż trzech par porównań, bo przedział za każdym razem maleje o połowę. Algorytm wykonuje od 1 do 6 porównań.

Najczęstsze błędy

• Wyszukiwanie binarne na nieposortowanej liście. Algorytm nie zgłosi błędu, tylko po cichu odpowie “brak” dla elementu, który na liście jest. Najpierw posortuj dane, np. sortowaniem przez wstawianie albo funkcją sorted().
• Warunek lewy < prawy zamiast lewy <= prawy. Gdy przedział skurczy się do jednego elementu, pętla kończy się przed jego sprawdzeniem i gubi trafienie.
• lewy = srodek zamiast lewy = srodek + 1. Środek już sprawdziliśmy; bez + 1 (i - 1 po drugiej stronie) przedział potrafi przestać maleć i pętla kręci się w nieskończoność.
• Minimum zaczynane od zera. Start od 0 zamiast od dane[0] daje zły wynik, gdy wszystkie liczby są dodatnie (minimum) albo ujemne (maksimum).
• Mylenie indeksu z wartością. Funkcja zwraca pozycję (indeks od zera), a nie sam element. Do wypisania wartości użyj dane[pozycja].

Ćwicz w przeglądarce

W temacie “Wyszukiwanie liniowe i binarne” kursu Algorytmy z podstawy programowej czekają trzy przykłady do krokowania i trzy zadania, które sprawdzają się automatycznie po uruchomieniu:

• pozycja elementu wyszukiwaniem liniowym (bez index()),
• ile razy występuje element (bez count()),
• wyszukiwanie binarne z liczeniem kroków.

Przycisk Krok wykonuje jedną linię, a panel obok pokazuje aktualne wartości lewy, prawy i srodek, więc widać, jak przedział kurczy się o połowę. W wersji z funkcją Krok wchodzi do jej środka, a stos wywołań pokazuje, skąd została wywołana. Dalsze algorytmy z tego samego kursu: sortowanie przez wybieranie oraz sortowanie przez wstawianie. Pełna lista: algorytmy z podstawy programowej.

Dla nauczycieli

Para “liniowe kontra binarne” świetnie pokazuje, że dobór algorytmu ma znaczenie: uczniowie liczą kroki obu metod na tych samych danych i sami widzą różnicę między n a log2(n). W BitWizards przydzielasz kurs klasie, udostępniasz tematy stopniowo i widzisz przebieg pisania kodu każdego ucznia (podgląd na żywo i odtwarzanie historii). Platforma jest darmowa dla szkół - jak zacząć. Więcej o tym, gdzie algorytmy leżą w podstawie programowej: informatyka w szkole.