Dvejetainės paieškos algoritmai paaiškinti naudojant C ++

Dvejetainė paieška yra vienas iš tų algoritmų, su kuriais susidursite kiekvienoje (geroje) įvadinėje informatikos pamokoje. Tai efektyvus algoritmas, leidžiantis surasti elementą užsakytame sąraše. Dėl šio pavyzdžio mes tiesiog manysime, kad tai yra masyvas.

Dvejetainės paieškos tikslai yra šie:

  • sugebėti išmesti pusę masyvo kiekvienoje iteracijoje
  • sumažinti elementų, kuriuos turime patirti, skaičių
  • palikite mums vieną galutinę vertę

Paimkime, pavyzdžiui, šį sveikųjų skaičių masyvą:

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

Tarkime, mes bandome rasti 7 masyvo indekso reikšmę. Iš viso yra 17 elementų, o indekso vertės yra nuo 0 iki 16.

Matome, kad indekso 7 vertė yra 4, nes tai yra penktasis masyvo elementas.

Bet koks būtų geriausias būdas kompiuteriui surasti ieškomo numerio indekso vertę?

Pirma, mes saugome minir maxreikšmes, tokias kaip 0ir 16.

int min = 0;int max = 16;

Dabar turime sugalvoti spėjimą. Protingiausia būtų atspėti indekso vertę masyvo viduryje.

Kai indekso reikšmė šiame masyve yra nuo 0 iki 16, šio masyvo vidurinė indekso vertė bus 8. Tai reiškia skaičių 14.

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

int guess = (min + max) / 2;

Mūsų spėjimas dabar lygus 8, kuris yra 14 masyvo, nes array[8]yra lygus 14.

Jei skaičius, kurio ieškojome, buvo 14, mes baigsime!

Kadangi taip nėra, dabar mes išmeskite pusę masyvo. Tai visi skaičiai po 14 arba indekso reikšmė 8, nes žinome, kad 14 yra didesnis nei 7, o mūsų spėjimas yra per didelis.

Po pirmojo kartojimo mūsų paieška dabar yra: 1, 3, 4, 6, 7, 8, 10, 13

Mes neprivalome atspėti paskutinėje pirminio masyvo pusėje, nes žinome, kad visos tos vertės yra per didelės. Štai kodėl svarbu taikyti dvejetainę paiešką tvarkomam sąrašui.

Kadangi mūsų pradinis spėjimas iš 14 buvo didesnis nei 7, dabar jį sumažiname 1 ir saugome max:

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

Dabar paieška atrodo taip:

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

Kadangi mūsų spėjimas buvo per mažas, mes atmetame apatinę masyvo pusę, padidindami min, atvirkščiai, nei tai darėme anksčiau max:

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

Iki kitos iteracijos mums lieka:

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

Kadangi 5 indekso vertė grąžina 8, dabar mes esame vienas virš savo tikslo. Mes pakartojame procesą dar kartą ir mums lieka:

 7min = 4max = 4guess = 4

Mums liko tik viena reikšmė - 4, kaip ieškomo tikslo skaičiaus indeksas, kuris buvo 7.

Dvejetainių paieškų tikslas yra atsikratyti pusės masyvo kiekvienoje kartojime. Taigi mes dirbame tik su tomis vertybėmis, apie kurias prasminga nuolat spėlioti.

Šio algoritmo pseudokodas atrodytų maždaug taip:

  1. Leiskite min = 0ir tegul max = nkur nyra didžiausia įmanoma indekso vertė
  2. Raskite vidurkį minir max, suapvalinkite žemyn, kad jis būtų sveikas skaičius. Tai yra mūsųguess
  3. Jei atspėjom skaičių, sustok, gavom!
  4. Jei guessyra per mažai, nustatykite minlygią daugiau neiguess
  5. Jei guessyra per didelis, nustatykite maxlygią vienai mažiau neiguess
  6. Grįžkite prie antro žingsnio.

Štai sprendimas, parašytas C ++: