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)
caz mediu Θ(log n)
cel mai rău caz O(log n)
memorie O(1)

Ce înseamnă acești termeni?

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.
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.

mijloc (mid)
găsit
exclus
țintă

0 / 14 pași

Fiecare mijloc pe care căutarea l-ar putea alege; o rulare e un drum în jos. Niveluri: 5 = ⌈log₂(24 + 1)⌉, cele mai multe comparații de care poate avea nevoie.

Viteză 8 pași/s

Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.

Î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.