Căutare liniară vs. binară
Căutare liniară vs. binară este un experiment interactiv din Algoritmi în acțiune, o simulare gratuită din StudyFi Lab care rulează direct în browser.
Căutarea liniară verifică elementele unul câte unul, așa că în cel mai rău caz are nevoie de n pași — O(n). Căutarea binară funcționează doar pe un tablou sortat: se uită la mijloc și, în funcție de rezultat, elimină o jumătate întreagă. După fiecare pas rămâne cel mult jumătate, deci ajung cel mult ⌈log₂(n+1)⌉ pași — O(log n). Pentru 40 de elemente sunt 6 pași în loc de 40.
Încearcă: Setează 40 de elemente și caută ultima valoare. Apoi alege un număr care nu este în tablou — câți pași îi trebuie fiecărei căutări ca să afle asta?
Întrebări frecvente
Ce arată experimentul „Căutare liniară vs. binară”?
Căutarea liniară verifică elementele unul câte unul, așa că în cel mai rău caz are nevoie de n pași — O(n). Căutarea binară funcționează doar pe un tablou sortat: se uită la mijloc și, în funcție de rezultat, elimină o jumătate întreagă. După fiecare pas rămâne cel mult jumătate, deci ajung cel mult ⌈log₂(n+1)⌉ pași — O(log n). Pentru 40 de elemente sunt 6 pași în loc de 40.
Cum încerc „Căutare liniară vs. binară”?
Setează 40 de elemente și caută ultima valoare. Apoi alege un număr care nu este în tablou — câți pași îi trebuie fiecărei căutări ca să afle asta?
Înveți pentru un test?
Încarcă-ți notițele și StudyFi le transformă în flashcarduri, teste și podcasturi.