ALGORYTMICZNA PRZYGODA
Kaliny

Archiwum

Polecam

Platformy do rozwiązywania zadań:
Strony do nauki:

Wyszukiwanie binarne

Cześć!
Czy słyszeliście kiedyś o wyszukiwaniu binarnym? Jest to bardzo przyjemny, a zarazem niezwykle przydatny algorytm, który zapewne wykorzystacie w niejednym zadaniu. Dzisiaj za pomocą pozornie prostego, a jednak dającego do myślenia programu wytłumaczę Wam ideę tego wspaniałego "przepisu".

#include <bits/stdc++.h>
using namespace std;
    
int main() {
	cout << "Pomysl o jakiejs liczbie od 1 do 100. Program bedzie ja zgadywal.\n";
	cout << "Jesli Twoja liczba jest wieksza od podanej przez program, napisz >\n";
	cout << "Natomiast jesli jest mniejsza, napisz <\n";
	cout << "Jesli program zgadl, napisz =\n";
	cout << "Gwarantuje, ze program nie zapyta Cie wiecej niz 7 razy.\n";
	 
int poczatek = 0, koniec = 101, srodek = poczatek+((koniec-poczatek)/2); char odp = ' '; while(odp!='=') { cout << srodek << "\n"; cin >> odp; if(odp=='<') { koniec = srodek; } if(odp=='>') { poczatek = srodek; } srodek = poczatek+((koniec-poczatek)/2); } return 0; }

Możecie śmiało skopiować ten kod i przetestować go na swoich kompilatorach. Niezależnie, o jaką liczbę go zapytacie, zawsze znajdzie ją w maksimum 7 krokach. Jak to możliwe?
Otóż zaprezentowany powyżej kod jest prostą implementacją algorytmu wyszukiwania binarnego. Na czym to polega? Postaram się przedstawić to w postaci takiej grafiki:

Wyszukiwanie binarne

Aby można było znaleźć jakąś liczbę (albo dane o innym typie, np. char) za pomocą wyszukiwania binarnego, ciąg danych musi być posortowany. Jest to najważniejszy warunek, który taki ciąg musi spełnić. Wtedy, jak pewnie zauważyliście, za każdym razem zmniejszamy zakres naszych poszukiwań o połowę. Z czego to wynika? Jeśli wiemy, że środek aktualnie przeszukiwanego ciągu jest np. mniejszy od szukanej liczby, to nie ma sensu przejmować się liczbami w lewej połowie. Mogłabym się tu rozpisać i dokładnie opisać każdy krok, jednak największy użytek (a zresztą i satysfakcję!) ma się z informacji, do których doszło się samodzielnie. Powodzenia!

O blogu

Zapraszam na moją algorytmiczną przygodę!

  • przygotowuję się do Olimpiady Informatycznej Juniorów oraz do Konkursu Logia;
  • biorę udział w Olimpijskim Kole Informatycznym;
  • pokonuję algorytmiczne trudności;
  • piszę programy w C++ i w Pythonie;
  • dzielę się swoimi przemyśleniami oraz pomysłami.
  • Ostatnie posty