- Valoarea căutată
- Încă posibile
- Comparate
- Excluse
- Găsite
Căutarea binară
Căutarea binară găsește o valoare într-o listă sortată uitându-se mereu la mijloc. Dacă valoarea din mijloc e prea mică, valoarea căutată poate fi doar după ea; dacă e prea mare, doar înaintea ei. Oricum, jumătate din ce a rămas e eliminată. Alegeți valoarea căutată, parcurgeți căutarea pas cu pas și urmăriți cum zona umbrită se micșorează până când valoarea e găsită sau nu mai rămâne nimic. Apăsați Redare pentru a urmări căutarea sau Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași ca să săriți oriunde. Linia întreruptă arată valoarea căutată, iar zona umbrită este locul unde mai poate fi. Căutarea binară are nevoie de o listă sortată, așa că o listă nesortată este sortată mai întâi. Alegeți valoarea, câte bare sunt sau introduceți propriile numere. Cu tabla selectată, săgețile avansează câte un pas, bara de spațiu pornește și pune pauză, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Alegeți valoarea căutată și câte bare sunt. Sau introduceți propriile numere: căutarea binară le sortează mai întâi.
- Apăsați Redare sau folosiți Pas și Înapoi ca să avansați câte un pas. Trageți glisorul pentru pași ca să săriți oriunde în căutare.
- Comparați caseta Comparații cu Necesar la căutarea liniară, pentru o valoare de lângă final sau una care lipsește.
Cum funcționează căutarea binară
Urmăriți partea din lista sortată în care valoarea căutată mai poate fi; la început, aceasta e toată lista. Priviți valoarea din mijlocul ei. Dacă e egală cu valoarea căutată, ați terminat. Dacă e mai mică, valoarea căutată poate fi doar după ea, așa că continuați cu partea de după mijloc. Dacă e mai mare, continuați cu partea dinainte. Când nu mai rămâne nimic, valoarea căutată nu e în listă.
De ce e atât de rapidă
Fiecare comparație înjumătățește partea rămasă. Pornind de la n valori, după k comparații rămân cel mult aproximativ n/2ᵏ, așa că o căutare se încheie după cel mult ⌊log₂ n⌋ + 1 comparații: 6 pentru 40 de valori, 10 pentru 1.000, 20 pentru un milion. Căutarea liniară poate fi nevoită să se uite la fiecare valoare. Problema e că lista trebuie să fie sortată, iar menținerea ei sortată, sau sortarea ei mai întâi, are propriul cost.
Întrebări frecvente
Cum funcționează căutarea binară?
Compară valoarea căutată cu valoarea din mijloc a părții dintr-o listă sortată în care aceasta mai poate fi. Egalitatea înseamnă că a fost găsită; altfel, jumătatea în care nu poate fi este eliminată, iar căutarea continuă în cealaltă jumătate până când valoarea e găsită sau nu mai rămâne nimic.
Câte comparații necesită căutarea binară?
Cel mult ⌊log₂ n⌋ + 1 pentru o listă de n valori: 6 pentru 40, 10 pentru 1.000, 20 pentru un milion. Fiecare comparație înjumătățește ce a rămas.
De ce are nevoie căutarea binară de o listă sortată?
Pentru că doar într-o listă sortată o singură comparație vă spune de ce parte e valoarea căutată. Într-o listă nesortată, o valoare mai mică la mijloc nu spune nimic despre locul valorii căutate, deci nu se poate elimina nimic.
Ce valoare găsește când există duplicate?
Oricare dintre ele, în funcție de unde cad mijloacele. Variantele care continuă să caute la stânga sau la dreapta după o potrivire găsesc prima sau ultima apariție.
Sunt numerele mele trimise undeva?
Nu. Căutarea rulează în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor