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 min
og max
værdier som 0
og 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:
- Lad
min = 0
, og ladmax = n
hvorn
er den højest mulige indeksværdi - Find gennemsnittet af
min
ogmax
, rund ned, så det er et heltal. Dette er voresguess
- Hvis vi gætter på antallet, så stop, vi fik det!
- Hvis den
guess
er for lav, skal du indstillemin
lig med en mere endguess
- Hvis den
guess
er for høj, skal du indstille denmax
til en mindre endguess
- Gå tilbage til trin to.
Her er en løsning, skrevet i C ++: