Ganska ofta programmerare, till och med nybörjare,står inför det faktum att det finns en uppsättning siffror där det är nödvändigt att hitta ett visst antal. Denna samling kallas en array. Och för att hitta det önskade elementet i det finns det många sätt. Men det enklaste bland dem är binär sökning. Vad är den här metoden? Och hur implementerar du binär sökning? Pascal är den enklaste miljön för att organisera ett sådant program, så vi kommer att använda det för att studera.
Låt oss först titta på vad som är fördelarna med den här metoden, för på så sätt kan vi förstå
Så, vad är principen för dettametod? Det bör sägas genast att binär sökning inte fungerar i någon matris, utan bara i en sorterad uppsättning siffror. Vid varje nästa steg tas mittelementet i matrisen (vilket betyder med elementnumret). Om det önskade antalet är större än genomsnittet kan allt som finns till vänster, det vill säga mindre än mittelementet, kasseras och inte sökas där. Och tvärtom, om det är mindre än genomsnittet - bland dessa siffror till höger kan du inte söka. Låt oss sedan välja ett nytt sökområde, där det första elementet kommer att vara mittelementet i hela matrisen, och det sista förblir det sista. Medelantalet för det nya området kommer att vara ¼ för hela segmentet, det vill säga (det sista elementet + mittelementet för hela arrayen) / 2. Återigen utförs samma operation - jämförelse med arrayens genomsnitt. Om det önskade värdet är mindre än genomsnittet kasserar vi höger sida och gör detsamma vidare tills det här mittelementet visar sig vara önskat.
Naturligtvis är det bäst att titta på ett exempel på hur binär sökning skrivs. Alla Pascal kommer att göra här - versionen är inte viktig. Låt oss skriva ett enkelt program.
Den innehåller en matris från 1 till h"massiv", variabel som anger den nedre gränsen för sökningen med namnet "niz", den övre gränsen med namnet "verh", den mellersta söktermen med namnet "sredn"; och det erforderliga antalet är "isk".
Så först tilldelar vi de övre och nedre gränserna för sökintervallet:
niz: = 1;
verh: = h + 1;
Sedan organiserar vi cykeln "medan den nedre är mindre än den övre gränsen":
Medan niz <verh - 1 gör
Börja
Vid varje steg delar vi segmentet med 2:
sredn: = (niz + verh) div 2; {använd div-funktion eftersom vi delar utan resten}
Varje gång vi kollar. Om genomsnittet är lika med önskat avbryter vi slingan, eftersom det nödvändiga elementet redan har hittats:
om sredn = isk då bryts;
Om mittelementet i matrisen är större än önskat, kasta vänster sida, det vill säga tilldela mittelementet till den övre gränsen:
om massiv [sredn]> isk då verh: = sredn;
Och om tvärtom, gör vi det till den nedre gränsen:
annars niz: = sredn;
slutet;
Det är allt som kommer att finnas i programmet.
Låt oss se hur den binära metoden kommer att se ut i praktiken. Låt oss ta en matris så här: 1, 3, 5, 7, 10, 12, 18 och leta efter siffran 12 i den.
Totalt har vi 7 element, så mitten blir den fjärde, dess värde är 7.
| 1 | 3 | 5 | 7 | 10 | 12 | 18 |
Eftersom 12 är större än 7 kan vi kasta bort elementen 1,3 och 5. Sedan har vi fyra siffror kvar, 4/2 utan att resten är 2. Så det nya mittelementet blir 10.
| 7 | 10 | 12 | 18 |
Här är mittelementet redan 12, detta är önskat nummer. Uppgift slutförd - nummer 12 hittat.
