szukaj(12) → indeks 5

Algorytmy wyszukiwania

Jak znaleźć jedną wartość wśród miliona.

Projektowanie oprogramowania  ·  rozdział 1.2  ·  klasa II
// milion elementów? wystarczy 20 porównań
Po co to komu

Szukanie jest wszędzie

Ctrl+F w edytorze

znajdź słowo w pliku

Wyszukiwarka

fraza wśród miliardów stron

Logowanie

czy taki login istnieje w bazie?

Gra online

czy nick jest już zajęty?

Obiecane w 1.1: sortowaliśmy nie dla sztuki — dziś zobaczysz, że w posortowanych danych szuka się błyskawicznie.
Metoda 1

Wyszukiwanie liniowe

Najprostszy pomysł: idź po tablicy od początku i porównuj każdy element z szukanym. Działa na każdej tablicy — także nieposortowanej.

czy 5 == 8?
5
2
8
1
nie → idziemy dalej
czy 2 == 8?
5
2
8
1
nie → idziemy dalej
czy 8 == 8?
5
2
8
1
tak! wynik: indeks 2
Pech: gdy elementu nie ma, sprawdzimy wszystkie n elementów — i dopiero wtedy to wiemy.
Metoda 1 — implementacja

Wyszukiwanie liniowe — kod

int szukaj(int t[], int n, int x) {
  for (int i = 0; i < n; i++) {
    if (t[i] == x)
      return i;   // znaleziono
  }
  return -1;      // nie ma
}

Jak to czytać:

  • zwracamy indeks pierwszego trafienia
  • return kończy pętlę od razu — nie szukamy dalej
  • -1 to umowny sygnał „nie znaleziono”

// wersja tego algorytmu „z wartownikiem” pojawiła się na egzaminie INF.04

Pytanie kontrolne: dlaczego sygnałem błędu jest -1, a nie 0?
Metoda 2

Wyszukiwanie binarne — pomysł

Gra: zgadnij liczbę od 1 do 100. Na każde pytanie odpowiadam tylko „za mało” albo „za dużo”. Najlepsza strategia? Zawsze pytaj o środek — każda odpowiedź odrzuca połowę kandydatów.

100→50→25→13→ 7→4→2→1

7 pytań wystarczy na 100 liczb. 20 pytań — na milion.

Warunek konieczny: tablica musi być posortowana. Bez tego „za mało / za dużo” nic nie mówi o tym, w której połowie szukać.
Metoda 2 — na przykładzie

Binarne — krok po kroku

Szukamy 12 w posortowanej tablicy. Szare pola — już odrzucone.

start
1
3
5
8
9
12
15
7 kandydatów
środek: 8
1
3
5
8
9
12
15
8 < 12 → prawa połowa
środek: 12
1
3
5
8
9
12
15
12 == 12 → mamy!
wynik
1
3
5
8
9
12
15
indeks 5
2 porównania zamiast 6 przy szukaniu liniowym. Im większa tablica, tym większa przewaga.
Metoda 2 — implementacja

Wyszukiwanie binarne — kod

int szukajBin(int t[], int n, int x) {
  int l = 0, p = n - 1;
  while (l <= p) {
    int s = (l + p) / 2;  // środek
    if (t[s] == x) return s;
    if (t[s] < x)  l = s + 1;  // w prawo
    else             p = s - 1;  // w lewo
  }
  return -1;
}

Jak to czytać:

  • l i p — granice przeszukiwanego fragmentu
  • s — środek fragmentu
  • każdy obrót pętli zostawia połowę
  • koniec, gdy granice się miną (l > p)
Pytanie kontrolne: prześledź działanie dla tablicy [1, 3, 5] i x = 4. Co zwróci funkcja?
Porównanie

Ile to kosztuje?

Najgorszy przypadek — element na końcu albo w ogóle go nie ma.

ElementówLinioweBinarne
1010 porównań4 porównań
1 0001 000 porównań10 porównań
1 000 0001 000 000 porównań20 porównań
To dlatego sortowaliśmy w 1.1: raz posortowana tablica zwraca się przy każdym wyszukiwaniu. Ten duet lubi wracać na egzaminie INF.04.
Praca własna

Zadanie

1 Na kartce

  • wyszukaj binarnie 21 w tablicy:
    [2, 4, 7, 10, 15, 21, 30]
  • w każdym kroku zapisz l, p i środek
  • policz porównania

2 W kodzie

  • zaimplementuj szukaj() i szukajBin()
  • dodaj do obu licznik porównań
  • porównaj liczniki dla tej samej tablicy

★ Dla szybkich

Uruchom szukajBin() na tablicy NIEposortowanej. Kiedy jeszcze trafia, a kiedy się myli? Dlaczego?

Podsumowanie

Zapamiętaj

Liniowe

sprawdzaj po kolei — działa na każdej tablicy, do n porównań.

Binarne

dziel na pół — tylko na posortowanej tablicy, ok. log₂(n) porównań.

Wynik

indeks znalezionego elementu albo -1, gdy go nie ma.

Sortowanie (1.1) + wyszukiwanie (1.2) = fundament algorytmiki, który wraca na egzaminie INF.04.