Algorytm wyszukiwania w zbiorze danych
Uczeń zapisuje algorytm wyszukiwania jako ciąg jednoznacznych kroków i porównuje liczbę kroków szukania po kolei oraz przez połowienie zakresu na tym samym zbiorze danych.
Sprzęt na lekcję: laptopy szkolne z przeglądarką i dostępem do internetu, po jednym na parę uczniów, projektor lub monitor do pokazu, wydruk karty pracy z listą 16 numerów inwentarza dla każdej pary, długopisy. Edytor Scratch otwiera się w przeglądarce bez zakładania konta pod adresem scratch.mit.edu/projects/editor. Jeśli szkolna sieć blokuje ten adres, część komputerową robi się w dowolnym arkuszu kalkulacyjnym zainstalowanym na laptopie, a przy braku laptopów działa wariant bez sprzętu.
Podstawa programowa
Informatyka · Szkoła podstawowa, klasy VII i VIIICele kształcenia, wymagania ogólne
- I Rozumienie, analizowanie i rozwiązywanie problemów na bazie logicznego i abstrakcyjnego myślenia, myślenia algorytmicznego i sposobów reprezentowania informacji.
Treści nauczania, wymagania szczegółowe
- I.1 formułuje problem w postaci specyfikacji (czyli opisuje dane i wyniki) oraz wyróżnia kroki w algorytmicznym rozwiązywaniu problemów. Stosuje różne sposoby przedstawiania algorytmów, w tym w języku naturalnym, w postaci listy kroków; Pełne pokrycie wątku zapisu algorytmu: specyfikacja (dane i wyniki) oraz przedstawianie algorytmu w postaci listy kroków.
- I.2 b) wyszukiwania i porządkowania: wyszukuje element w zbiorze nieuporządkowanym oraz porządkuje elementy w zbiorze metodą przez proste wybieranie; Uwaga na brzmienie, ważna przy rozmowie z nauczycielem. Wersja z 2024 r. (Dz.U. 2024 poz. 996) mówi tylko o wyszukiwaniu elementu "w zbiorze nieuporządkowanym". Pierwotne brzmienie z 2017 r. obejmowało zbiór uporządkowany i nieuporządkowany. Wyszukiwanie przez połowienie zakresu w zbiorze uporządkowanym nie ma dziś oparcia w podstawie dla klas VII i VIII. Wraca ono do klas VII i VIII z nową podstawą (Dz.U. 2026 poz. 378, wymaganie 1.4) oraz występuje w szkole ponadpodstawowej w zakresie rozszerzonym. Wyszukiwanie po kolei jest pokryte w pełni.
Nowa podstawa programowa, Dz.U. 2026 poz. 378
Ta lekcja realizuje wymagania nowej podstawy, zanim staną się obowiązkowe, czyli od rok szkolny 2029/2030 (klasa VII) i 2030/2031 (klasa VIII).
- 1.4 stosuje podstawowe algorytmy do wyszukiwania, zliczania i porządkowania danych, w tym wyszukiwanie w ciągu uporządkowanym i nieuporządkowanym oraz porządkowanie przez wybór lub metodą bąbelkową; Obejmuje wyszukiwanie w ciągu uporządkowanym, czyli wątek połowienia zakresu.
Czego uczy ta lekcja
- Zapis algorytmu w krokach
- Wyszukiwanie po kolei i przez połowienie
To jest lekcja otwarta.
Cały komplet widzicie bez logowania: scenariusz, prezentacja, karta pracy, materiały dla ucznia i quiz. Tak samo wygląda każda lekcja w katalogu po uruchomieniu szkoły.
Film dla nauczyciela
Lektor omawia każdy slajd i podpowiada, na co uważać w klasie. Głos lektora jest syntetyczny, wygenerowany przez AI.
Materiały lekcji
Każdy materiał otwieracie w przeglądarce albo pobieracie jako PDF gotowy do wydruku.
- Scenariusz lekcji PDF: Scenariusz lekcji, plik do pobrania
- Prezentacja na tablicę Otwórz: Prezentacja na tablicę PDF: Prezentacja na tablicę, plik do pobrania
- Karta pracy do druku Otwórz: Karta pracy do druku PDF: Karta pracy do druku, plik do pobrania
- Materiały dla ucznia Otwórz: Materiały dla ucznia PDF: Materiały dla ucznia, plik do pobrania
- Kartka dla rodzica PDF: Kartka dla rodzica, plik do pobrania
- Quiz Otwórz: Quiz PDF dla ucznia: Quiz, plik do pobrania PDF z odpowiedziami: Quiz, plik do pobrania
Wszystko w jednym pliku
Scenariusz, prezentacja, karta pracy, materiały dla ucznia i quiz w obu wersjach.
Lista kontrolna przed lekcją
Do odhaczenia dzień wcześniej i 10 minut przed dzwonkiem. Zaznaczenia zostają tylko w tej przeglądarce i nigdzie się nie zapisują.
Rozgrzewka na start
Powiedzcie klasie: „Zgubiłem długopis gdzieś w tej sali. Podajcie mi instrukcję szukania go tak dokładnie, żeby wykonał ją robot, który nie wie, co to długopis ani sala”. Zapiszcie na tablicy pierwsze trzy propozycje dosłownie, tak jak padły.
Czego się spodziewać: Uczniowie zaczynają od zdań typu „rozejrzyj się” albo „sprawdź pod ławkami”, a po dopytaniu „którą ławkę pierwszą, a którą drugą” sami dochodzą do tego, że instrukcja musi mieć kolejność, numerowane miejsca i moment, w którym wolno przestać szukać. To trzy cechy algorytmu, do których wrócicie na slajdzie drugim.
Przebieg lekcji
-
5 min
Wejście
Nauczyciel zapisuje w notatniku liczbę z zakresu od 1 do 1000 i zaprasza klasę do zgadywania. Po każdej próbie odpowiada tylko „za mało” albo „za dużo”, a na tablicy stawia kreskę za każde pytanie. Gra kończy się zwykle po mniej niż piętnastu pytaniach. Nauczyciel pyta: ile pytań trzeba by zadać, gdybyśmy sprawdzali po kolei 1, 2, 3 i tak dalej. Odpowiedź tysiąc zostaje na tablicy obok liczby kresek. Zapowiada, że przez najbliższe 40 minut klasa zapisze regułę dobrego zgadywania tak dokładnie, żeby wykonał ją ktoś, kto nic o niej nie wie.
-
10 min
Pokaz
Nauczyciel wyświetla uporządkowaną rosnąco listę 16 numerów inwentarza ze szkolnej biblioteki: 1042, 1087, 1130, 1156, 1199, 1204, 1233, 1290, 1315, 1342, 1388, 1401, 1455, 1470, 1512, 1560. Na tablicy zapisuje dwa algorytmy jako ponumerowane kroki. Algorytm A, szukanie po kolei: 1. Ustaw pozycję na 1. 2. Porównaj numer na tej pozycji z szukanym. 3. Jeśli równy, wypisz pozycję i zakończ. 4. Jeśli pozycja to 16, wypisz „nie ma” i zakończ. 5. Zwiększ pozycję o 1 i wróć do kroku 2. Algorytm B, połowienie zakresu: 1. Ustaw dolną na 1, górną na 16. 2. Jeśli dolna jest większa od górnej, wypisz „nie ma” i zakończ. 3. Ustaw środek na wynik dzielenia sumy dolnej i górnej przez 2, zaokrąglony w dół. 4. Porównaj numer ze środka z szukanym. 5. Jeśli równy, wypisz środek i zakończ. 6. Jeśli numer ze środka jest mniejszy, ustaw dolną na środek plus 1, w przeciwnym razie ustaw górną na środek minus 1. 7. Wróć do kroku 2. Nauczyciel wykonuje algorytm B na głos dla numeru 1401 i dochodzi do wyniku w 2 krokach, potem dla numeru 1300, którego na liście nie ma, i pokazuje, że po 4 krokach dolna przekracza górną, więc algorytm kończy się odpowiedzią „nie ma”. Podkreśla trzy cechy dobrego zapisu: każdy krok jednoznaczny, warunek zakończenia obecny, wynik podany także wtedy, gdy danej nie ma.
-
20 min
Praca uczniów
Część pierwsza, 8 minut na papierze. Pary wykonują oba algorytmy z tablicy dla trzech numerów: 1199, 1560 oraz 1305, którego na liście nie ma. Do tabeli w karcie pracy wpisują liczbę kroków dla algorytmu A i dla algorytmu B oraz wynik. Jeden uczeń czyta kroki na głos, drugi wykonuje je dosłownie i nie wolno mu niczego domyślić. Część druga, 12 minut na laptopach. Pary otwierają scratch.mit.edu/projects/editor i budują skrypt, w którym to komputer zgaduje liczbę pomyślaną przez ucznia z zakresu od 1 do 100. Potrzebne zmienne: dolna, gorna, strzal, proby. Środek liczy się blokiem „podłoga z” (zaokrąglenie w dół), nie zwykłym blokiem „zaokrąglij”, bo ten zaokrągla 5,5 do 6 i liczba prób przestaje się zgadzać z algorytmem z tablicy. Szkielet skryptu jest wypisany blok po bloku w karcie pracy. Para testuje skrypt na trzech różnych liczbach i zapisuje największą liczbę prób, jaka jej wyszła. Projekt zapisuje się poleceniem Plik, a następnie Zapisz na swoim komputerze, więc konto nie jest potrzebne. Nauczyciel chodzi po sali i sprawdza przede wszystkim, czy pary poprawnie zwężają zakres o jeden.
-
5 min
Sprawdzenie
Nauczyciel rysuje na tablicy tabelę z trzema szukanymi numerami i dwiema kolumnami na liczbę kroków. Trzy pary podają swoje wyniki, klasa porównuje. Dla numeru 1199 algorytm A potrzebuje 5 kroków, a B 4, dla numeru 1560 odpowiednio 16 i 5, dla nieobecnego 1305 algorytm A wykonuje 16 kroków, bo przechodzi całą listę i dopiero po ostatnim porównaniu wypisuje „nie ma”, a B kończy po 4 krokach. Nauczyciel pyta, dlaczego przy numerze 1199 przewaga połowienia prawie znika, i doprowadza klasę do odpowiedzi, że szukana dana leży blisko początku listy. Potem pyta o zbiór tysiąca pozycji i o zbiór miliona pozycji. Klasa dochodzi do liczb: do 10 kroków przy tysiącu i do 20 kroków przy milionie, bo każdy krok zmniejsza zakres o połowę.
-
5 min
Podsumowanie
Nauczyciel wraca do gry z początku lekcji i pyta, czy klasa zgadywała zgodnie z algorytmem B. Zapisuje wniosek w trzech zdaniach: algorytm to kroki na tyle jednoznaczne, że wykonuje je ktoś bez wiedzy o zadaniu, każdy algorytm musi mieć warunek zakończenia, a połowienie działa tylko na zbiorze uporządkowanym. Dodaje uwagę praktyczną: uporządkowanie zbioru też kosztuje czas, więc przy jednym szukaniu w krótkiej liście prostsze jest szukanie po kolei. Zapowiada kolejną lekcję o bazach danych, na której klasa zaprojektuje tabelę biblioteki, czyli zbiór, w którym takie szukanie ma sens.
Do powiedzenia na głos
„Algorytm to nie pomysł w głowie. To kroki zapisane tak dokładnie, że wykona je ktoś, kto o zadaniu nie wie nic.”
„Za chwilę Wasz kolega będzie wykonywał Wasze kroki dosłownie. Jeśli w którymś miejscu musi się domyślić, to ten krok jest źle napisany.”
„Każdy algorytm musi umieć się skończyć także wtedy, gdy szukanej danej po prostu nie ma.”
„Połowienie zakresu działa tylko na liście uporządkowanej. Na liście w przypadkowej kolejności daje złą odpowiedź, a nie wolniejszą.”
Typowe błędy uczniów
- Uczniowie stosują połowienie do listy w przypadkowej kolejności i dziwią się, że wynik jest błędny. Wprowadźcie krok zerowy: sprawdź, czy lista jest uporządkowana, i dopiero wtedy wybieraj algorytm.
- W zapisie algorytmu brakuje warunku zakończenia dla danej, której nie ma, więc wykonanie kręci się w kółko. Wymagajcie wprost kroku „jeśli dolna jest większa od górnej, wypisz nie ma i zakończ”.
- Pary liczą kroki różnymi sposobami, jedni porównania, drudzy podziały zakresu, i wyniki się nie zgadzają. Ustalcie na tablicy jedną definicję kroku przed rozpoczęciem pracy i trzymajcie ją do końca lekcji.
- Część uczniów zaokrągla środek w górę, część w dół, więc te same dane dają różne liczby kroków. Zapiszcie regułę zaokrąglania w dół obok algorytmu i wracajcie do niej przy sprawdzaniu.
- W Scratchu uczniowie ustawiają dolną na wartość strzału zamiast na strzał plus 1, przez co zakres przestaje się kurczyć i skrypt pyta w nieskończoność. Pokażcie to na przykładzie zakresu od 5 do 6, gdzie środek zawsze wypada na 5.
Warianty lekcji
Bez sprzętu i internetu
Nauczyciel przygotowuje 16 kartek z numerami inwentarza z listy z lekcji, układa je na ławce w kolejności rosnącej numerami do dołu i podpisuje pozycje od 1 do 16. Jeden uczeń jest wykonawcą algorytmu i może odwrócić tylko tę kartkę, którą wskazuje bieżący krok. Drugi uczeń czyta kroki na głos z kartki, a trzeci liczy odwrócone kartki, czyli kroki. Klasa przeprowadza w ten sposób oba algorytmy dla tych samych trzech numerów co w karcie pracy: 1199, 1560 i 1305 i zapisuje wyniki w tabeli na tablicy. Wniosek wychodzi identyczny, a dodatkowo widać, że wykonawca nie ma prawa podejrzeć całej listy, dokładnie tak jak komputer.
Dla szybszych uczniów
Para wyznacza największą możliwą liczbę kroków połowienia dla zbiorów o wielkości 100, 1000 i 1 000 000 pozycji, zapisuje regułę słowami i sprawdza ją na swoim skrypcie, zmieniając górną granicę zakresu. Następnie dopisuje do skryptu kontrolę uczciwości: jeśli dolna przekroczy górną, a gracz nie powiedział „trafione”, program wypisuje komunikat, że podane odpowiedzi są sprzeczne. Para wyjaśnia w dwóch zdaniach, dlaczego ten sam warunek w algorytmie wyszukiwania oznacza „danej nie ma w zbiorze”.
Przy trudnościach
Uczeń pracuje na skróconej liście ośmiu numerów: 1042, 1130, 1199, 1233, 1315, 1388, 1455, 1512, i szuka tylko jednego numeru wskazanego przez nauczyciela. Kroki algorytmu B dostaje wydrukowane z dwiema lukami do uzupełnienia zamiast pełnego zapisu. W części komputerowej otwiera przygotowany przez nauczyciela plik projektu i wstawia dwa brakujące bloki, zamiast budować cały skrypt od zera. Liczbę kroków zapisuje w gotowej tabeli z podpisanymi wierszami.
Klucz do karty pracy
Klucz odpowiedzi do karty pracy jest w koncie nauczyciela i w PDF dla nauczyciela.
Kryteria oceny
Trzy poziomy dla każdej umiejętności. Opis mówi, co uczeń pokazuje, a nie ile punktów dostaje.
| Umiejętność | Podstawowy | Dobry | Bardzo dobry |
|---|---|---|---|
| Zapis algorytmu w krokach | Uczeń przepisuje z tablicy algorytm połowienia jako ponumerowane kroki i wskazuje krok, który kończy działanie, gdy danej nie ma. | Uczeń zapisuje własnymi słowami oba algorytmy z lekcji tak, że kolega wykonuje je dosłownie bez pytań, z jedną nazwą dla każdej zmiennej i regułą zaokrąglania. | Uczeń znajduje w cudzym zapisie krok niejednoznaczny albo brakujący warunek zakończenia, pokazuje na przykładzie danych, co się przez to psuje, i poprawia zapis. |
| Wyszukiwanie po kolei i przez połowienie | Uczeń wykonuje oba algorytmy na liście 16 numerów dla podanego numeru i poprawnie liczy kroki jako porównania. | Uczeń wypełnia całą tabelę dla trzech numerów, w tym nieobecnego, i tłumaczy, dlaczego przy numerze z początku listy przewaga połowienia prawie znika. | Uczeń wyznacza największą liczbę kroków połowienia dla zbioru 1000 i miliona pozycji regułą podwajania i uzasadnia, kiedy mimo to wybrałby szukanie po kolei, wskazując koszt porządkowania. |
Pytania do dyskusji
Na podsumowanie lekcji. Nie mają jednej poprawnej odpowiedzi, chodzi o uzasadnienie.
-
Papierowy słownik i katalog biblioteki są uporządkowane, a półka z grami w domu zwykle nie. Co decyduje o tym, czy warto ponosić koszt porządkowania?
-
Kiedy zgadywaliście liczbę na początku lekcji, ktoś zaproponował pytanie o środek zakresu i część klasy protestowała. Dlaczego pytanie o środek wydaje się gorsze, skoro jest najlepsze?
-
Czy zapis kroków dla człowieka i dla komputera powinien wyglądać tak samo? Co człowiek dopowie sobie sam, a czego komputerowi nie wolno pominąć?
Częste pytania uczniów
Mini projekt na kolejne lekcje
Na 2 do 3 kolejne lekcje albo na kółko. Buduje na tym, co uczniowie zrobili dzisiaj.
Wyszukiwarka w katalogu klasowej biblioteczki
Klasa buduje w Scratchu prosty katalog z listą uporządkowanych numerów i wyszukiwarką, która działa połowieniem i pokazuje liczbę wykonanych kroków. Projekt zajmuje dwie do trzech lekcji albo dwa spotkania kółka i buduje na skrypcie zgadywania z tej lekcji.
Etapy
- Lekcja 1: para spisuje 20 do 30 rzeczywistych tytułów z klasowej półki albo z domu, nadaje im numery i porządkuje listę rosnąco na kartce, a potem wpisuje numery do listy w Scratchu (kategoria Zmienne, przycisk Utwórz listę).
- Lekcja 2: para przerabia skrypt zgadywania z tej lekcji tak, żeby zamiast pytać gracza, sam porównywał szukany numer z elementem listy na pozycji strzal i zwężał zakres; wynikiem jest pozycja albo komunikat „nie ma”.
- Lekcja 3: para dopisuje licznik kroków i drugi przycisk z szukaniem po kolei, po czym dla pięciu numerów zapisuje w tabeli, ile kroków zajęła każda metoda.
- Prezentacja: każda para pokazuje klasie jeden numer, przy którym połowienie wygrało wyraźnie, i jeden, przy którym różnica była mała, i tłumaczy dlaczego.
Co powstaje na końcu: Działający projekt Scratch z listą numerów, dwiema metodami wyszukiwania i licznikiem kroków oraz tabela porównawcza dla pięciu numerów, gotowa do pokazania na następnej lekcji o bazach danych.
Dla rodzica
Krótka wiadomość do przekazania przez dziennik albo do wydruku na wywiadówkę. Ten sam tekst jest w PDF „Kartka dla rodzica”.
Czego dziecko nauczyło się na tej lekcji: Wasze dziecko potrafi zapisać sposób rozwiązania zadania jako ponumerowane kroki, które da się wykonać bez domyślania, i wie, że taki zapis musi umieć się zakończyć. Umie też porównać dwie metody szukania w uporządkowanej liście i policzyć, że w zbiorze tysiąca pozycji wystarczy około dziesięciu sprawdzeń.
Pytanie na kolację: Pomyślę liczbę od 1 do 100, a Ty zgadnij ją w jak najmniejszej liczbie pytań. Powiesz mi potem, dlaczego zawsze pytasz o środek?
PDF dla rodzica: kartka dla rodzica, plik do pobraniaWideo dla nauczyciela
Nagranie powstaje na podstawie tego skryptu. Do czasu publikacji wideo możecie przeczytać skrypt przed lekcją.
| Czas | Treść |
|---|---|
| 0:00 do 0:45 | Przedstawiam cel lekcji dla nauczyciela. W 45 minut uczeń zapisze algorytm wyszukiwania jako listę kroków i porówna dwie metody szukania na tym samym zbiorze. Nie potrzebujecie umieć programować. Potrzebujecie tablicy, wydrukowanej karty pracy i laptopów z przeglądarką. |
| 0:45 do 1:40 | Zaczynacie od gry. Zapisujecie liczbę od 1 do 1000 i pozwalacie klasie zgadywać, odpowiadając wyłącznie za mało albo za dużo. Kreska na tablicy za każde pytanie. Gra kończy się po kilkunastu pytaniach i to jest Wasz punkt odniesienia na całą lekcję. Nie tłumaczcie jeszcze niczego, niech klasa sama zobaczy liczbę kresek. |
| 1:40 do 2:50 | Przechodzę przez pokaz. Wyświetlacie szesnaście numerów inwentarza uporządkowanych rosnąco i zapisujecie na tablicy dwa algorytmy numerowanymi krokami. Kluczowe jest to, żeby zapisać je krokami, a nie opisać zdaniami. Uczniowie mają je przepisać i potem wykonać dosłownie, więc każde niedopowiedzenie wróci do Was w pytaniu ucznia. |
| 2:50 do 3:50 | Zwracam uwagę na warunek zakończenia. Wykonajcie połowienie dla numeru, którego na liście nie ma. Po czterech krokach dolna granica przekracza górną i algorytm odpowiada, że danej nie ma. To jest moment, w którym klasa rozumie, po co w ogóle zapisuje się taki warunek. W pracach uczniów brakuje go najczęściej. |
| 3:50 do 5:00 | Omawiam pracę uczniów. Pierwsze osiem minut na papierze, w parach, jeden czyta kroki, drugi je wykonuje i nie wolno mu się niczego domyślać. Kolejne dwanaście minut w edytorze Scratch, gdzie para buduje skrypt zgadujący liczbę od 1 do 100. Edytor działa bez zakładania konta, a projekt zapisuje się na dysk poleceniem Plik, a potem Zapisz na swoim komputerze. |
| 5:00 do 5:55 | Najczęstsza usterka w skrypcie to ustawienie dolnej granicy na wartość strzału zamiast na strzał plus 1. Zakres przestaje się wtedy kurczyć i program pyta w nieskończoność. Sprawdzajcie ten jeden blok przy każdej parze, bo to on odpowiada za większość zgłoszeń, że nie działa. |
| 5:55 do 6:40 | Na sprawdzeniu zbieracie liczby kroków do wspólnej tabeli. Dla numeru z początku listy przewaga połowienia prawie znika i to jest najlepszy materiał na dyskusję. Potem pytacie o tysiąc i o milion pozycji. Odpowiedzi to do dziesięciu i do dwudziestu kroków, a klasa dochodzi do nich samodzielnie przez podwajanie. |
| 6:40 do 7:00 | Zamykam. Wynikiem lekcji nie jest działający skrypt, tylko zapis algorytmu, który da się wykonać bez domyślania, i świadomość, że połowienie potrzebuje uporządkowanego zbioru. To zdanie prowadzi wprost do kolejnej lekcji o bazach danych. |
Podoba się Wam ta lekcja?
Po uruchomieniu szkoły nauczyciel zapisuje przeprowadzenie lekcji jednym kliknięciem, a dyrektor dostaje z tego raport wykorzystania sprzętu.
Zgłoś szkołę do pilotażu