V razvoju programske opreme se nizi uporabljajo povsod. "Inteligentni" tipi podatkov v sodobnih programskih jezikih, kot so dinamični nizi, nudijo velike možnosti za priročno delo s predmeti. Ampak algoritmi, ki so podlaga za delo s temi vrstami podatkov, ki so bili razviti ob zori računalništva - sredi dvajsetega stoletja. Prvi algoritem za binarno iskanje je bil objavljen leta 1946. Razmislite o najbolj priljubljenih algoritmih za ravnanje z nizi.

Zaporedno iskanje

To je najpreprostejši algoritem za iskanje vrednosti v matriki. Uporablja metodo izmenične primerjave elementov matrike s ključno vrednostjo. Ponavadi poteka od leve proti desni. Uporablja se, če so elementi v polju nekoliko izven seznama. Popolnoma neučinkovito v velikih nizih, kjer se običajno uporabljajo binarna iskanja. Algoritem deluje na naslednji način:

Primerjaj vrednost ključa z vrednostjo elementa matrike.

Če so vrednosti enake, vrnemo dobljeno vrednost.

Če ne, povečamo vrednost spremenljivke cikla za eno in jo primerjamo z naslednjim elementom matrike.

Indeksno zaporedno iskanje

Učinkovitejši način za iskanje vrednosti v razvrščenem nizu. Ampak bolj zahtevna za vire.

Binarno iskanje

Binarno (binarno) iskanje je algoritem za iskanje elementa matrike z zaporedno delitvijo polja na polovico in primerjavo izhoda s številko iz sredine polja.Če je število iz sredine manjše od želenega, poglejmo še v drugem delu, če več - nadaljujemo iskanje v prvem. Algoritem je najhitrejši od vseh naštetih in deluje na naslednji način:

Najprej ugotovimo vrednost predmeta v sredini polja. Preverite, da se ujema z izvirno vrednostjo.

Če je vrednost iz sredine manjša od izvirne, nadaljujemo iskanje v drugi polovici, če več - iščemo prvo.

V končni polovici nadaljujte na enak način: razdelite ga za polovico in primerjajte pridobljeno vrednost.

Iskanje poteka, dokler začetna vrednost ne postane enaka vrednosti v matriki. Če se to ne zgodi, potem ta vrednost v matriki ne obstaja. Pri oblikovanju binarnega iskanja lahko naletimo na več pasti.

Prelivanje izbranega podatkovnega tipa

Da bi našli vrednost na sredini matrike, morate narediti desno in levo vrednost in jo razdeliti na dva. To je:sredina polja = leva vrednost + (leva vrednost - vrednost desno) /2

Med delovanjem dodajanja obstaja nevarnost prelivanja podatkovnega tipa. Če je polje tako veliko, morate uporabiti različne tehnike, da se izognete tveganju. Spodaj so standardne napake pri načrtovanju binarnih iskanj.

Napake vrednosti

Ali napake na enoto. Zelo pomembno je upoštevati naslednje možnosti:

• Prazno polje.
• Ni vrednosti.
• Prekoračitev polja.

Več kopij

Opozoriti je treba, daV primeru obstoja več enakih primerkov ključa v matriki mora program najti določen (prvi, zadnji, naslednji).

Oglejmo si implementacijo tega algoritma v programskem jeziku C plus plus. Upoštevajte, da binarno iskanje deluje samo z razvrščenim nizom! Če matrika ni predhodno razvrščena, bo rezultat izračuna napačen.

V nadaljevanju je koda na C ++. Sprva se niz začetnih spremenljivk za celo število, velikost deset, inicializira. Nato operater cin v zanki čaka na vnos desetih vrednosti od uporabnika (vrstica deset).

V dvajseti vrstici program od uporabnika pričakuje, da vnese vrednost ključa.

Vrstice 29 - 35 predstavljajo uveljavljeni algoritem binarnega iskanja. Med izvajanjem programa v srednji spremenljivki se vrednost povprečnega elementa zapiše na naslednji način:

Sredina polja (sredina) = (leva vrednost (l) + desna vrednost (r)) /2

Vrstica

arr [sredina] == tipkaPreveri se, ali je srednja vrednost ključna vrednost. Če je ena, se vrednost zastave zastave spremeni v TRUE, kar pomeni, da je problem rešen. Če je srednja vrednost večja od vrednosti našega ključa, se desna stran (spremenljivka r) dodeli sredi. ČeNasprotno, sredina je postavljena v r. Slednji preverja zastavo boolean zastave.

Prednosti binarnega iskanja

Če želite hitro operacijo programa, morate uporabiti binarno iskanje. In za pisanje takšnega algoritma ne bo bolelo niti začetnik programer. Vendar je zelo pomembno, da se upoštevajo vsi skrajni primeri: izven meja polja, odsotnost želene vrednosti, napaka pri prelivanju podatkov.

Slabosti

Za pravilno delovanje algoritma mora biti polje predhodno razvrščeno. V ta namen lahko uporabite funkcijo ready sort () v programskem jeziku C ++. In še ena pomembna točka, ki jo je treba iskati pri proučevanju binarnega iskanja v C in C ++. Ta algoritem se lahko uporablja samo z nekaterimi podatkovnimi strukturami. Na primer, strukture, ki uporabljajo povezane sezname, tukaj niso primerne.