Klasa 4 · rozdział 5 · lekcje 27–30

Wyszukiwanie liniowe i binarne

Liniowe idzie od początku i działa przy dowolnej kolejności. Binarne skacze do środka, ale dane muszą być posortowane. Brak elementu to −1. Ten rozdział zamyka I okres: stos, ONP, NWD, sito i oba wyszukiwania.

Po tym rozdziale powinieneś umieć

  • zaimplementować oba algorytmy jako funkcje bez we/wy;
  • podać warunek binarnego: tablica rosnąca;
  • obsłużyć brak elementu, pustą tablicę, jeden element oraz końce zakresu;
  • porównać liczbę porównań i nazwać to O(n) oraz O(log n);
  • schować tablicę w klasie i szukać metodą;
  • powtórzyć, co z I okresu wchodzi na ocenę śródroczną.

1. Wyszukiwanie liniowe

Porównujesz szukaną wartość z kolejnymi elementami, od indeksu 0. Pierwsze trafienie — zwracasz indeks. Koniec bez trafienia — zwracasz −1. Żaden poprawny indeks nie jest ujemny, więc −1 da się odróżnić od „jest na początku”.

// Nazwa: szukaj
// Opis: wyszukiwanie liniowe, pierwsze trafienie
// Parametry: t — tablica, n — liczba elementów, x — szukana wartość
// Zwraca: indeks albo -1
// We/wy: brak
int szukaj(const int t[], int n, int x) {
    for (int i = 0; i < n; i++)
        if (t[i] == x) return i;
    return -1;
}

int a[] = { 4, 7, 1, 7, 3 };
cout << szukaj(a, 5, 7);    // 1
cout << szukaj(a, 5, 9);    // -1
cout << szukaj(a, 0, 4);    // -1, pusta tablica

Kolejność elementów jest dowolna. Siódemka występuje dwa razy — funkcja staje na pierwszej. Ostatnie trafienie to osobna pętla od końca albo zapamiętany indeks. Brak elementu nie jest wyjątkiem.

2. Binarne — warunki

Gdy tablica jest posortowana rosnąco, środek przedziału mówi, której połowy nie trzeba oglądać. Środek równy szukanej wartości — to indeks. Środek za mały — prawa połowa. Za duży — lewa. Przedział musi się zmniejszać: po sprawdzeniu środka wypadasz z niego (lewy = srodek + 1 albo prawy = srodek - 1). Inaczej pętla może stanąć w miejscu.

Tylko na posortowanej Ta sama funkcja na {4, 7, 1, 7, 3} może zwrócić −1, choć jedynka w tablicy jest. Algorytm zakłada, że na lewo od środka są wartości mniejsze. Bez sortowania założenie jest fałszywe. Najpierw układ danych (następny rozdział), albo zostań przy liniowym.

Warunki, które sprawdzasz, zanim nazwiesz wynik binarnym:

  • dane rosnące (równe elementy obok siebie są dopuszczalne, byle nie malały);
  • szukasz wartości, nie „pierwszego większego”, o ile tak nie napiszesz osobnej wersji;
  • umowa braku to −1, tak samo jak w liniowym.

3. Binarne — implementacja i brzegi

// Nazwa: szukajBin
// Opis: wyszukiwanie binarne w tablicy posortowanej rosnąco
// Parametry: t, n, x
// Zwraca: indeks albo -1
// We/wy: brak
int szukajBin(const int t[], int n, int x) {
    int lewy = 0, 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;
}

Ślad szukania 11 w {1, 4, 7, 11, 15, 20}:

  1. lewy 0, prawy 5, środek 2, wartość 7. 7 < 11, lewy = 3.
  2. lewy 3, prawy 5, środek 4, wartość 15. 15 > 11, prawy = 3.
  3. lewy 3, prawy 3, środek 3, wartość 11. Trafienie, indeks 3.

Brzegi, które uruchamiasz osobno:

  • pusta tablica, n = 0 — pętla się nie zaczyna (prawy = -1), wynik −1;
  • jeden element: trafienie na indeksie 0 albo −1;
  • szukana na lewym końcu (1) i na prawym (20) — indeksy 0 i 5;
  • wartość między elementami, na przykład 5 — −1, przedział się schodzi.

szukajBin dla 20 kończy na indeksie 5. Dla 5 schodzi w lewo od siódemki i kończy z lewym większym od prawego.

4. O(n) i O(log n)

Liniowe w najgorszym razie ogląda wszystkie n elementów: O(n). Binarne w każdym kroku wyrzuca około połowy przedziału. Dla 1000 elementów cięcia 512, 256, …, 1 to około 10 porównań, nie 1000. To O(log n) — logarytm o podstawie 2 z n, czyli „ile razy da się przepołowić”.

LinioweBinarne
DaneDowolna kolejnośćRosnące
Najgorzejn porównańokoło log₂ n porównań
1 000 elementówdo 1 000około 10
Brak elementu−1−1
ZapisO(n)O(log n)

Na małym przykładzie liczysz porównania palcem. Tablica sześcioelementowa, szukane 11: binarne zrobiło trzy porównania równości (7, 15, 11). Liniowe na tej samej, już ułożonej tablicy doszłoby do indeksu 3 i zrobiło cztery porównania (1, 4, 7, 11). Przy sześciu elementach różnica jest mała. Przy tysiącu — nie. Dlatego „binarne jest szybsze” bez słowa „posortowane” jest półprawdą. Sortowanie, którego binarne wymaga, też kosztuje — o tym jest następny rozdział.

5. Wyszukiwanie w klasie

Tablica albo vector może być polem prywatnym. Metoda zwraca indeks, main wypisuje. Algorytm się nie zmienia. Zmienia się to, kto ma prawo ruszyć dane.

class Katalog {
    vector<int> kody;   // trzymane rosnąco
public:
    void dodajNaKoniec(int k) { kody.push_back(k); }
    int znajdz(int x) const {
        int lewy = 0, prawy = (int)kody.size() - 1;
        while (lewy <= prawy) {
            int s = (lewy + prawy) / 2;
            if (kody[s] == x) return s;
            if (kody[s] < x) lewy = s + 1;
            else prawy = s - 1;
        }
        return -1;
    }
};

Metoda zakłada porządek. Jeśli dodajNaKoniec wstawi liczbę burzącą wzrost, wynik binarny kłamie. Albo dopisujesz tylko wartości nie mniejsze od ostatniej, albo sortujesz przed szukaniem. Liniowa metoda w tej samej klasie nie ma tego warunku — i przy trzydziestu kodach często wystarcza.

6. Podsumowanie I okresu

Ocena śródroczna bierze lekcje 1–30. Z tego podręcznika są to rozdziały 1–5.

  • Układ funkcji bez we/wy, nagłówek, friend z uzasadnieniem, szablon i specjalizacja, szablon kontra virtual.
  • Kod zwrotny albo wyjątek, własny typ, lista błędów, bez pustego catch.
  • Stos i kolejka, ONP na kartce i w programie, stacja rozrządowa, błędne wyrażenie.
  • NWD, NWW, sito, ułamek, nazwy O(1), O(log n), O(n), O(n²) na przykładach.
  • Oba wyszukiwania, brzegi, O(n) kontra O(log n).

II okres (rozdziały 6–10) dokłada sortowanie ze scalaniem, szyfry, metody numeryczne, wzorce i zadanie zbiorcze. Braki z I okresu da się uzupełnić później, ale śródroczna ich nie pomija.

Jedno zdanie na odpowiedź ustną „Binarne, bo kody są rosnące i jest ich dużo.” „Liniowe, bo kolejność jest dowolna.” „ONP liczę stosem, bo operator bierze dwa ostatnie argumenty.”

Ćwiczenia do samodzielnego wykonania

Folder: Dokumenty\cwiczenia-po\klasa-4\rozdzial-05.

Ćwiczenie 1. Liniowe łatwe

szukaj na {4, 7, 1, 7, 3}. Wyniki dla 7, 3 i 9: 1, 4, −1. Osobno ostatnie trafienie siódemki: 3.

Ćwiczenie 2. Ślad binarny średnie

Na kartce lewy, prawy i środek przy szukaniu 20 oraz 5 w {1, 4, 7, 11, 15, 20}. Indeksy: 5 i −1.

Ćwiczenie 3. Brzegi średnie

Testy: n = 0, tablica {5} szukaj 5 i 6, pierwszy i ostatni element tablicy z rozdziału. Wszystkie funkcje bez we/wy.

Ćwiczenie 4. Liczba porównań średnie

Dla szukania 11 policz porównania liniowe i binarne. Dopisz zdanie z O(n) i O(log n) dla n = 1000.

Ćwiczenie 5. Katalog trudne

Klasa z prywatnym vectorem kodów rosnących i metodą binarną. Drugi test: wstaw kod, który psuje porządek, i pokaż zły wynik. Napisz, co musiałoby się stać, żebyś przeszedł na liniowe.

Ćwiczenie 6. Kartka I okresu trudne

Bez komputera: NWD(48, 18), ONP 2 3 +, LIFO po dwóch poloz, oraz czy binarne wolno puścić na nieposortowanej tablicy. Cztery krótkie odpowiedzi.

Sprawdź się

1. Wyszukiwanie liniowe:
2. Po sprawdzeniu środka, gdy jest za mały:
3. Pusta tablica i brak elementu:
4. Przy 1000 posortowanych elementach binarne w najgorszym razie:
5. I okres (ocena śródroczna) obejmuje:

Wymagania na ocenę

Dział 5 planu (lekcje 27–30) oraz domknięcie I okresu. Ocena wyższa zawiera wymagania na oceny niższe.

OcenaUczeń
2 Omawia wyszukiwanie liniowe i binarne na poziomie idei. Wie, że binarne wymaga posortowanych danych.
3 Implementuje wyszukiwanie liniowe. Implementuje binarne według wzoru na tablicy posortowanej.
4 Oba algorytmy są funkcjami bez we/wy. Obsługuje „nie znaleziono”. Porównuje liczbę porównań na małym przykładzie.
5 Programuje wyszukiwanie metodą klasy. Charakteryzuje O(n) i O(log n). Testuje element na brzegu i tablicę jednoelementową oraz pustą.
6 Uzasadnia, kiedy liniowe wystarcza. Łączy późniejsze sortowanie z binarnym, jeśli ten fragment jest już zrobiony, albo pokazuje, co psuje porządek w klasie Katalog.

Lista „już umiem”