Računala » Binarno pretraživanje - analiza algoritma u C ++

Binarno pretraživanje - analiza algoritma u C ++

Računala

U razvoju softvera, polja se koriste svugdje. "Inteligentni" tipovi podataka u suvremenim programskim jezicima, kao što su dinamički nizovi, pružaju velike mogućnosti za praktičan rad s objektima. No, algoritmi na kojima se temelji rad s ovim vrstama podataka koji su razvijeni u zoru računalne znanosti - sredinom dvadesetog stoljeća. Prvi algoritam za binarno pretraživanje objavljen je 1946. Razmotrite najpopularnije algoritme za rukovanje nizovima.

Sekvencijalno pretraživanje

Ovo je najjednostavniji algoritam za pronalaženje vrijednosti u nizu. Koristi metodu naizmjenične usporedbe elemenata niza s ključnom vrijednošću. Obično se radi s lijeva na desno. Koristi se ako su stavke u nizu malo izvan popisa. Apsolutno neučinkovito u velikim nizovima, gdje se obično koriste binarna pretraživanja. Algoritam radi na sljedeći način:


  • Usporedite vrijednost ključa s vrijednošću elementa polja.
  • Ako su vrijednosti jednake, vraćamo dobivenu vrijednost.
  • Ako nije, povećavamo vrijednost varijable ciklusa za jednu i uspoređujemo je sa sljedećim elementom polja.

    • Indeksno-sekvencijalno pretraživanje

    Učinkovitiji način za pronalaženje vrijednosti u sortiranom nizu. Ali zahtjevnije za resursima.

    Binarno pretraživanje

    Binarno (binarno) pretraživanje je algoritam za pronalaženje elementa niza tako da se niz dijeli na pola i uspoređuje izlaz s brojem iz sredine polja.Ako je broj iz sredine manji od željenog, gledamo dalje, u drugom dijelu, ako više - nastavljamo potragu u prvom. Algoritam je najbrži od svih navedenih i radi na sljedeći način:


  • Najprije ćemo otkriti vrijednost objekta u sredini niza. Provjerite odgovara li izvornoj vrijednosti.
  • Ako je vrijednost iz sredine manja od izvorne, onda nastavljamo potragu u drugoj polovici, ako više - tražimo prvu.
  • U rezultatskoj polovici postupite na isti način: podijelite ga za polovicu i usporedite dobivenu vrijednost.
    • Pretraživanje se odvija dok početna vrijednost ne postane jednaka vrijednosti u nizu. Ako se to ne dogodi - onda ova vrijednost u nizu ne postoji.
    Postoji nekoliko zamki koje se mogu susresti pri dizajniranju binarnog pretraživanja.

    Prekoračenje odabranog tipa podataka

    Da biste pronašli vrijednost u sredini niza, morate napraviti desnu i lijevu vrijednost i podijeliti s dva. To je:Sredina polja = Lijeva vrijednost + (Lijeva vrijednost - vrijednost desno) /2

    Postoji opasnost od prelijevanja tipa podataka tijekom operacije dodavanja. Ako je niz toliko velik, morate koristiti različite tehnike kako biste izbjegli rizik. U nastavku su navedeni standardni bugovi pri dizajniranju binarnih pretraživanja.

    Pogreške vrijednosti

    Ili pogreške po jedinici. Vrlo je važno razmotriti sljedeće opcije:

    • Prazan niz.
    • Nema vrijednosti.
    • Prekoračenje polja.

    Više primjeraka

    Treba napomenuti daU slučaju postojanja nekoliko identičnih primjeraka ključa u nizu, program mora pronaći određeni (prvi, zadnji, sljedeći).


    & lt; script type = "text /javascript" & gt;
    može blockSettings2 = {blockId: "R-A-271049-5", renderTo: "yandex_rtb_R-A-70350-39", async: 0};
    if (document.cookie.indexOf ("abmatch =") & gt; = 0) blockSettings2.statId = 70350;
    Funkcija (a, b, c, d, e) {a [c] = a [c] || [], a [c] .push (funkcija () {Ya.Context.AdvManager.render (blockSettings2)}), e = b.getElementsByTagName ("script") , d = b.createElement ("script"), d.type = "text /javascript", d.src = "//an.yandex .ru /system /context.js ", d.async =! 0e.parentNode.insertBefore (d, e)} (ovaj, ovaj.dokument," yandexContextAsyncCallbacks ");

    Razmotrimo implementaciju ovog algoritma u programskom jeziku C plus plus. Imajte na umu da binarno pretraživanje radi samo s sortiranim nizom! Ako polje nije prethodno sortirano, rezultat izračuna će biti netočan.

    Slijedi kod na C ++. U početku se inicijalizira niz cjelobrojnih varijabli, veličina deset. Zatim, operator cin u petlji čeka na unos deset vrijednosti od korisnika (redak deset).

    U dvadesetom retku program očekuje da korisnik unese ključnu vrijednost.

    Linije 29 - 35 predstavljaju implementirani algoritam binarnog pretraživanja. Tijekom izvođenja programa u srednjoj varijabli, vrijednost prosječnog elementa piše se na sljedeći način:

    Medij niza (sredina) = (lijeva vrijednost (l) + desna vrijednost (r)) /2

    Red

    arr [mid] == tipkaProvjerava je li srednja vrijednost ključna vrijednost. Ako je jedna, vrijednost zastavice zastave mijenja se u TRUE, to jest, problem je riješen. Ako je srednja vrijednost veća od vrijednosti našeg ključa, desna strana (varijabla r) je dodijeljena sredini. akoNaprotiv, sredina se nalazi u r. Potonja provjerava zastavicu boolean zastavice.

    Prednosti binarnog pretraživanja

    Binarno pretraživanje treba koristiti ako vam je potrebna brza operacija programa. I napisati takav algoritam neće nauditi ni početnik programer. No, vrlo je važno uzeti u obzir sve ekstremne slučajeve: izvan granica polja, odsutnost željene vrijednosti, pogrešku prelijevanja podataka.

    Nedostaci

    Za ispravan rad algoritma, polje mora biti unaprijed sortirano. Da biste to učinili, možete koristiti funkciju ready sort () u programskom jeziku C ++. I još jedna važna stvar koju treba tražiti kada proučavamo binarno pretraživanje u C i C ++. Ovaj se algoritam može koristiti samo s određenim strukturama podataka. Na primjer, strukture koje koriste povezane popise ovdje nisu prikladne.

    Povezane publikacije