Căutare binară (explicarea algoritmului) - Programare C++ (31)
ฝัง
- เผยแพร่เมื่อ 30 ส.ค. 2022
- Probleme și lecții de informatică gratuite: infoas.ro
ℹ Despre acest videoclip
În acest episod vorbim despre algoritmul de căutare binară. De asemenea, vedem de ce este mult mai eficient decât algoritmul clasic de căutare într-un vector (numit și „căutare liniară”), după care implementăm algoritmul în CodeBlocks în C++ și rezolvăm câteva probleme de pe platforma de informatică InfoAs.
Fără îndoială, informatica este industria de viitor. În această serie abordăm programa școlară a informaticii în C++, cu ajutorul căreia poți să obții nota 10 la teste sau la bac!
📖 Alte resurse utile
"C++ | Partea 33 | Cautare Binara #1" (Zecelainfo): • C++ | Partea 33 | Caut...
"Cautarea binara in vectori" (Invata.info): • Cautarea binara in vec...
"Binary search in 3 minutes" (Michael Sambol): • Video
💬 Contact
Ai nelămuriri? Lasă un comentariu sau scrie-ne pe infoas.ro/contact !
a doua problema (comenzi) se putea rezolva cu interclasare nu?
Da, dacă mai întâi sortezi cele două șiruri. Cu toate acestea, cu căutare binară obții un algoritm mai eficient:
Căutare binară - O((m + n) log n)
Interclasare - O(n log n + m log m + n + m)
În concluzie, faci aproximativ n + m mai mulți pași decât căutarea binară.