Binaarne otsingu algoritm koos EXAMPLE'iga

Enne binaarotsingu õppimist õpime:

Mis on otsing?

Otsing on utiliit, mis võimaldab selle kasutajal leida andmebaasis olevaid dokumente, faile, meediume või mis tahes muud tüüpi andmeid. Otsing töötab lihtsal põhimõttel, et kriteeriumid sobitatakse kirjetega ja kuvatakse see kasutajale. Sel viisil töötab kõige elementaarsem otsingufunktsioon.

Mis on binaarne otsing?

Binaarne otsing on täpsemat tüüpi otsingualgoritm, mis otsib ja hangib andmeid sorteeritud üksuste loendist. Selle põhitööpõhimõte hõlmab loendis olevate andmete jagamist pooleks, kuni vajalik väärtus on leitud ja kasutajale otsingutulemustes kuvatud. Binaarne otsing on üldtuntud kui a poole intervalliga otsing või logaritmiline otsing.

Kuidas binaarne otsing töötab?

Binaarne otsing toimib järgmiselt:

• Otsinguprotsess algab sorteeritud andmemassiivi keskmise elemendi leidmisega
• Pärast seda võrreldakse võtme väärtust elemendiga
• Kui võtme väärtus on keskmisest elemendist väiksem, analüüsib otsing ülemisi väärtusi keskmise elemendiga võrdluseks ja sobitamiseks
• Kui võtme väärtus on suurem kui keskmine element, analüüsib otsing keskmise elemendi madalamaid väärtusi võrdluseks ja sobitamiseks

Binaarse otsingu näide

Vaatame sõnastiku näidet. Kui teil on vaja leida teatud sõna, ei vaata keegi iga sõna järjestikku läbi, vaid otsib vajaliku sõna otsimiseks juhuslikult lähimad sõnad.

Ülaltoodud pilt illustreerib järgmist:

1. Teil on 10-kohaline massiiv ja element 59 tuleb leida.
2. Kõik elemendid on tähistatud indeksiga 0–9. Nüüd arvutatakse massiivi keskosa. Selleks võtke indeksi vasak- ja parempoolseim väärtus ning jagage need 2-ga. Tulemuseks on 4.5, kuid me võtame alamväärtuse. Seega on keskmine 4.
3. Algoritm langetab kõik elemendid keskmisest (4) madalaima piirini, kuna 59 on suurem kui 24, ja nüüd on massiivi ainult 5 elementi.
4. Nüüd on 59 suurem kui 45 ja väiksem kui 63. Keskmine on 7. Seega muutub parempoolse indeksi väärtus keskmiseks – 1, mis võrdub 6-ga, ja vasakpoolne indeksi väärtus jääb samaks, mis varem, mis on 5.
5. Siinkohal teate, et 59 tuleb pärast 45. Seega muutub ka vasakpoolne indeks, mis on 5, keskmiseks.
6. Need iteratsioonid jätkuvad seni, kuni massiiv väheneb ainult üheks elemendiks või leitav üksus muutub massiivi keskele.

Näiteks 2

Vaatame järgmist näidet, et mõista binaarotsingu toimimist

1. Teil on sorteeritud väärtuste massiiv vahemikus 2 kuni 20 ja peate leidma 18.
2. Alumise ja ülemise piiri keskmine on (l + r) / 2 = 4. Otsitav väärtus on suurem kui keskmine, mis on 4.
3. Keskmisest väiksemad massiivi väärtused jäetakse otsingust välja ja otsitakse keskmisest väärtusest 4 suuremaid väärtusi.
4. See on korduv jagamisprotsess, kuni tegelik otsitav üksus leitakse.

Miks me vajame binaarset otsingut?

Järgmised põhjused muudavad binaarse otsingu otsingualgoritmina paremaks valikuks.

• Binaarne otsing töötab tõhusalt sorteeritud andmetel, olenemata andmete suurusest
• Selle asemel, et otsida andmeid järjestikku läbides, pääseb binaaralgoritm vajaliku elemendi leidmiseks andmetele juhuslikult juurde. See muudab otsingutsüklid lühemaks ja täpsemaks.
• Binaarne otsing võrdleb sorteeritud andmeid järjestamise põhimõttel kui võrdusvõrdlusi kasutades, mis on aeglasemad ja enamasti ebatäpsed.
• Pärast iga otsingutsüklit jagab algoritm massiivi suuruse pooleks, seega töötab see järgmises iteratsioonis ainult ülejäänud massiivi pooles

Lugege meie järgmist õpetust Lineaarne otsing: Python, C++ Näide

kokkuvõte

• Otsing on utiliit, mis võimaldab selle kasutajal otsida dokumente, faile ja muud tüüpi andmeid. Binaarne otsing on täpsemat tüüpi otsingualgoritm, mis otsib ja hangib andmeid sorteeritud üksuste loendist.
• Binaarne otsing on tavaliselt tuntud kui poolintervallotsing või logaritmiline otsing
• See toimib, jagades massiivi pooleks iga kord, kui vajaliku elemendi all leitakse.
• . binaarne algoritm võtab massiivi keskkoha, jagades vasakpoolse ja parempoolseima indeksi väärtuste summa 2-ga. Nüüd langeb algoritm kas elementide alumise või ülemise piiri massiivi keskelt, olenevalt leitavast elemendist.
• Algoritm pääseb vajaliku elemendi leidmiseks andmetele juhuslikult juurde. See muudab otsingutsüklid lühemaks ja täpsemaks.
• Binaarne otsing võrdleb sorteeritud andmeid järjestuspõhimõtte alusel, mitte aga aeglase ja ebatäpse võrdõiguslikkuse võrdluse kasutamisel.
• Binaarne otsing ei sobi sortimata andmete jaoks.