Binarni algoritmi pretraživanja objašnjeni pomoću C ++

Binarno pretraživanje jedan je od onih algoritama s kojima ćete se susretati na svakom (dobrom) uvodnom satu informatike. To je učinkovit algoritam za pronalaženje predmeta na uređenom popisu. Radi ovog primjera pretpostavit ćemo da je ovo niz.

Ciljevi binarnog pretraživanja su:

  • biti u mogućnosti odbaciti polovicu niza u svakoj iteraciji
  • smanjiti broj elemenata kroz koje moramo proći
  • ostavi nam jednu konačnu vrijednost

Uzmimo za primjer sljedeći niz cijelih brojeva:

int array[] = { 1, 3, 4, 6, 7, 8, 10, 13, 14, 18, 19, 21, 24, 37, 40, 45, 71 };

Recimo da pokušavamo pronaći vrijednost indeksa broja 7 u ovom nizu. Ukupno ima 17 predmeta, a vrijednosti indeksa kreću se od 0 do 16.

Možemo vidjeti da je vrijednost indeksa 7 4, jer je to peti element u polju.

Ali koji bi bio najbolji način da računalo pronađe vrijednost indeksa broja koji tražimo?

Prvo, mi pohraniti mini maxvrijednosti, kao što su 0i 16.

int min = 0;int max = 16;

Sad moramo smisliti nagađanje. Najpametnije bi bilo pogoditi vrijednost indeksa u sredini polja.

S vrijednošću indeksa od 0 do 16 u ovom polju, srednja vrijednost indeksa ovog polja bila bi 8. To sadrži broj 14.

// This will round down if the quotient is not an integer

int guess = (min + max) / 2;

Naša pretpostavka je sada jednaka 8, što je 14 u nizu, jer array[8]je jednako 14.

Da je broj koji smo tražili 14, bili bismo gotovi!

Budući da to nije slučaj, sada ćemo odbaciti polovicu niza. To su svi brojevi nakon 14, odnosno vrijednosti indeksa 8, budući da znamo da je 14 veće od 7, a naša je pretpostavka previsoka.

Nakon prve iteracije, naša pretraga je sada unutar: 1, 3, 4, 6, 7, 8, 10, 13

Ne moramo pogađati u posljednjoj polovici izvornog niza, jer znamo da su sve te vrijednosti prevelike. Zbog toga je važno da na poredani popis primijenimo binarno pretraživanje .

Budući da je naša izvorna pretpostavka od 14 bila veća od 7, sada je smanjujemo za 1 i pohranjujemo u max:

max = guess - 1; // max is now equal to 7, which is 13 in the array

Sada pretraga izgleda ovako:

 1, 3, 4, 6, 7, 8, 10, 13
min = 0max = 7guess = 3 

Budući da je naša pretpostavka bila preniska, odbacujemo donju polovicu niza povećavajući min, obratno onome što smo prethodno radili max:

min = guess + 1; // min is now 4

Do sljedeće iteracije ostaje nam:

 7, 8, 10, 13min = 4max = 7guess = 5

Budući da vrijednost indeksa 5 vraća 8, sada smo jedan iznad cilja. Ponavljamo postupak i ostaje nam:

 7min = 4max = 4guess = 4

I ostaje nam samo jedna vrijednost, 4, kao indeks ciljnog broja koji smo tražili, a to je 7.

Svrha binarnog pretraživanja je riješiti se pola niza u svakoj iteraciji. Dakle, radimo samo na onim vrijednostima o kojima ima smisla nastaviti pogađati.

Pseudo-kôd za ovaj algoritam izgledao bi otprilike ovako:

  1. Neka min = 0i neka je max = ngdje nje najveća moguća vrijednost indeksa
  2. Pronađite prosjek mini max, zaokružite prema dolje tako da je cijeli broj. Ovo je našeguess
  3. Ako smo pogodili broj, stanite, dobili smo!
  4. Ako guessje prenizak, postavite ga minkao jedan veći odguess
  5. Ako guessje previsok, postavite ga maxjednako manjem odguess
  6. Vratite se koraku dva.

Evo rješenja napisanog na C ++: