Binære søgealgoritmer forklaret ved hjælp af C ++

Binær søgning er en af ​​de algoritmer, som du støder på på hver (god) indledende computervidenskabsklasse. Det er en effektiv algoritme til at finde en vare på en ordnet liste. Af hensyn til dette eksempel antager vi bare, at dette er en matrix.

Målet med binær søgning er at:

• være i stand til at kassere halvdelen af ​​arrayet ved hver iteration
• minimer antallet af elementer, vi skal igennem
• lad os have en endelig værdi

Tag for eksempel følgende matrix af heltal:

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

Lad os sige, at vi prøver at finde indeksværdien af ​​tallet 7 i denne matrix. Der er 17 poster i alt, og indeksværdierne går fra 0 til 16.

Vi kan se, at indeksværdien på 7 er 4, da det er det femte element i arrayet.

Men hvad ville være den bedste måde for computeren at finde indeksværdien af ​​det nummer, vi leder efter?

Først, vi gemme minog maxværdier som 0og 16.

int min = 0;int max = 16;

Nu er vi nødt til at komme med et gæt. Den smarteste ting at gøre ville være at gætte en indeksværdi midt i arrayet.

Med indeksværdien 0 til 16 i denne matrix ville den midterste indeksværdi for denne matrix være 8. Det holder tallet 14.

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

int guess = (min + max) / 2;

Vores gæt er nu lig med 8, hvilket er 14 i arrayet, da det array[8]er lig med 14.

Hvis antallet, vi ledte efter, var 14, ville vi være færdige!

Da det ikke er tilfældet, vil vi nu kassere halvdelen af ​​arrayet. Disse er alle tallene efter 14 eller indeksværdi 8, da vi ved, at 14 er større end 7, og vores gæt er for højt.

Efter den første iteration er vores søgning nu inden for: 1, 3, 4, 6, 7, 8, 10, 13

Vi behøver ikke gætte i den sidste halvdel af det oprindelige array, fordi vi ved, at alle disse værdier er for store. Derfor er det vigtigt, at vi anvender binær søgning på en ordnet liste.

Da vores oprindelige gæt på 14 var større end 7, reducerer vi det nu med 1 og gemmer det i max:

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

Nu ser søgningen sådan ud:

 1, 3, 4, 6, 7, 8, 10, 13

min = 0max = 7guess = 3 

Fordi vores gæt var for lavt, kasserer vi den nederste halvdel af arrayet ved at øge min, omvendt til hvad vi tidligere gjorde for at max:

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

Ved den næste iteration er vi tilbage med:

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

Da indeksværdi 5 returnerer 8, er vi nu en over vores mål. Vi gentager processen igen, og vi har tilbage med:

 7min = 4max = 4guess = 4

Og vi har kun én værdi, 4, som indekset for det målnummer, vi ledte efter, hvilket var 7.

Formålet med binær søgning er at slippe af med halvdelen af ​​arrayet ved hver iteration. Så vi arbejder kun på de værdier, som det giver mening at fortsætte med at gætte på.

Pseudokoden for denne algoritme ville se sådan ud:

1. Lad min = 0, og lad max = nhvor ner den højest mulige indeksværdi
2. Find gennemsnittet af minog max, rund ned, så det er et heltal. Dette er voresguess
3. Hvis vi gætter på antallet, så stop, vi fik det!
4. Hvis den guesser for lav, skal du indstille minlig med en mere endguess
5. Hvis den guesser for høj, skal du indstille den maxtil en mindre endguess
6. Gå tilbage til trin to.

Her er en løsning, skrevet i C ++: