Căutare binară
Găsește o valoare într-un tablou sortat uitându-se la mijloc și aruncând jumătatea în care nu poate fi. Fiecare comparație înjumătățește ce a rămas.
- cel mai bun caz Ω(1)
- Θ(log n)
- cel mai rău caz O(log n)
- memorie O(1)
log₂ n: de câte ori poți înjumătăți n până rămâne 1. Pentru 64 de valori e 6, deci cel mult 7 comparații.
Alți termeni de pe această pagină
- Sortat: în ordine crescătoare. Căutarea binară are nevoie de asta; pe date nesortate dă răspunsuri greșite.
- Înjumătățire: fiecare comparație aruncă jumătate din ce a rămas, jumătatea în care ținta nu poate fi.
- mijloc (mid)
- găsit
- exclus
- țintă
Încearcă: Alege o țintă care nu e în tablou. Căutarea tot se oprește după cel mult ⌈log₂(n + 1)⌉ comparații, când lo depășește hi.
Cum funcționează
Căutarea binară ține două repere, lo și hi, în jurul părții din tablou unde ținta mai poate fi. Se uită la valoarea din mijloc: dacă e ținta, gata; dacă e mai mică, ținta poate fi doar la dreapta, deci lo trece după mijloc; dacă e mai mare, hi trece înainte. Fiecare pas înjumătățește restul: 64 de valori cer cel mult 7 comparații, un milion cel mult 20. Când lo depășește hi, nu mai rămâne nimic: valoarea nu e în tablou.
Când este o alegere bună
Folosește căutarea binară ori de câte ori datele sunt sortate și poți sări la orice poziție: un cuvânt într-o listă sortată, o versiune într-un istoric, git bisect, locul de inserare într-un tablou sortat. Pe date nesortate dă răspunsuri greșite, iar sortarea înainte merită doar dacă cauți de multe ori.