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.
{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}:
- lewy 0, prawy 5, środek 2, wartość 7. 7 < 11, lewy = 3.
- lewy 3, prawy 5, środek 4, wartość 15. 15 > 11, prawy = 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ć”.
| Liniowe | Binarne | |
|---|---|---|
| Dane | Dowolna kolejność | Rosnące |
| Najgorzej | n porównań | około log₂ n porównań |
| 1 000 elementów | do 1 000 | około 10 |
| Brak elementu | −1 | −1 |
| Zapis | O(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,
friendz uzasadnieniem, szablon i specjalizacja, szablon kontravirtual. - 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.
Ć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ę
Wymagania na ocenę
Dział 5 planu (lekcje 27–30) oraz domknięcie I okresu. Ocena wyższa zawiera wymagania na oceny niższe.
| Ocena | Uczeń |
|---|---|
| 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. |