Binær søk i java

Å søke etter en matrise etter posisjonen til en verdi og sortere matrisen, er to forskjellige prosesser. Søk betyr å bekrefte om en verdi som kalles nøkkelen, finnes i matrisen. Sortering betyr å sette alle verdiene i matrisen i en bestemt rekkefølge (stigende eller synke). Hvis en matrise ikke er sortert og søket er nødvendig, må programmet starte fra indeks null, deretter til indeks 1, så indeks 2, og så videre, til det når indeksen for verdien den leter etter. Hvis verdien oppstår mer enn en gang, bør den første indeksen returneres.

Hvis matrisen er sortert først, si i stigende rekkefølge, blir søket enkelt. Indeksen er enten mindre enn indeksen for mellomelementet, hvis nøkkelen er mindre enn verdien av midtindeksen, eller indeksen er lik eller større enn midtindeksen, hvis verdien er lik eller større enn den for midtindeksverdien.

Så bare del matrisen i to. Hvis verdien ligger på venstre side, trenger du ikke å kaste bort tid på å søke på høyre side; Bare søk på venstre side. Hvis verdien ligger på høyre side, trenger du ikke å kaste bort tid på å søke på venstre side; Bare søk på høyre side. Siden matrisen allerede er sortert fullstendig, når hver side er kommet til, blir den delt igjen i to, og bare en av de nye siderparene blir søkt på. Å søke på denne måten er faktisk bare ved å dele seg i to, til indeksen for verdien er kommet til. Ingen faktisk søk ​​når det gjelder skanning foregår fordi matrisen allerede er sortert. Det kan være noe lite bevegelse til høyre, og noen svake bevegelige til venstre i matrisen under søket.

Binær innebærer, to. Og slik kalles denne typen søk. Det er forskjellige sorteringsordrer: alle verdiene i matrisen kan sorteres i stigende rekkefølge eller synkende rekkefølge helt. En matrise kan også sorteres i det som kalles binært søketreformat. Dette er ikke fullstendig sortering i stigende eller synkende rekkefølge. Imidlertid fungerer det binære algoritmesøket fremdeles med dette formatet.

Denne artikkelen forklarer Java Binary Search. Binær søkealgoritme i Java fungerer på en matrise som allerede er sortert. Bare fullstendig sortering i stigende rekkefølge vurderes i denne artikkelen. Denne artikkelen begynner med illustrasjon av den binære søkealgoritmen. Den fortsetter deretter med å forklare hvordan du bruker binarysearch () -metodene i Java Arrays -klassen.

Artikkelinnhold

• Illustrasjon av binær søkealgoritme
• Java -pakke og klasse for binær søk
• Konstruere matrisen for søk
• Binære søkemetoder i Arrays -klassen
• Søker etter et område
• Konklusjon

Illustrasjon av binær søkealgoritme

Tenk på følgende sekvens av tegn:

P v d q s x t h n o

Arrangerer i stigende rekkefølge, blir sekvensen:

D h n o p q s t v x

Det er ti elementer her. Indekstelling begynner fra 0. Når antall elementer er jevn (e.g., 10), blir indeksen for mellomelementet betraktet som antall elementer delt på to. I dette tilfellet er 10/2 5. Når antall elementer er merkelig, tas indeksen for midtelementet som heltallsdelen (hele antallet) av antall elementer delt på to.

Det er to lister ovenfor. Den andre er den sorterte formen for den første. Anta at søket skulle vite om S var til stede i den første listen. Listen må først sorteres for å ha den andre listen i det binære søkeordningen. I den sorterte listen er indeksen for mellomposisjonen 5 = 10/2. Dette tilsvarer verdien, q. Søket stopper da for å sjekke om Q er s, verdien så etter. Hvis det er det, stopper søket. Hvis det ikke er det, sjekker søket om S ligger mindre enn Q eller fra Q og oppover.

I dette tilfellet ligger det i området fra Q og oppover, som deretter blir valgt. Ingen tid blir bortkastet og søk i den nedre halvdelen av listen (matrise). Så dette nye området må deles inn i to. Dette området består av 5 elementer. 5/2 = 2 og en 1/2. Det midterste elementet er i posisjon 2 i dette nye området. Dette tilsvarer t, hvis telling fra null skal begynne fra q. Selve indeksen for T er 7.

Nedre eller venstre rekke. Er det nye mellomelementet, det samme som s, verdien så etter? - Nei. I hvilket område ligger s; er det i det nedre området, (q s) eller i det øvre området, (t v x)? - Det ligger i det nedre området.

Så det nedre området (Q s) må da deles inn i to. Når dette er gjort, tilsvarer midtindeksen for dette området S (2/2 = 1, da Q er på ny indeks 0). Selve indeksen for S er 6 (D er på den opprinnelige indeksen 0). Indeksen for den funnet verdien skal returneres.

Nøkkelen ikke funnet

Verdien som er sett etter kalles nøkkelen. Den sorterte listen har faktisk to indeksering som vist nedenfor:

D	H	N	O	P	Q	S	T	V	X
0	1	2	3	4	5	6	7	8	9
-1	-2	-3	-4	-5	-6	-7	-8	-9	-10

Den første raden i denne tabellen har den sorterte listen. Den andre raden har normal indeksering. Den tredje raden har en slags negativ indeksering der det første elementet er ved indeks -1, den andre er på indeks -2, den tredje på indeks -3, og så videre.

Hvis nøkkelen er funnet, vil Java -algoritmen returnere normalindeksen, fra 0. Hvis nøkkelen ikke blir funnet, vil Java -algoritmen returnere den negative indeksen for den posisjonen nøkkelen ville ha okkupert (forutsatt at matrisen utvidet til høyre med ett element).

Java -pakke og klasse for binær søk

Java Binary Search -ordningen fungerer på en matrise som allerede er sortert. Java -klasse -matriser, som er i Java.util.* pakke, har binarysearch () metoder for binær søking i en rekke som allerede er sortert. Hver av disse metodene returnerer et heltall som er en normal indeks hvis nøkkelen er funnet, eller en negativ indeks, som forklart ovenfor, hvis nøkkelen ikke er funnet. To av disse metodene er for chars.

Konstruere matrisen for søk

Den andre listen over vil bli brukt til å illustrere binær søkekoding i Java. Følgende uttalelse kan brukes til å konstruere den sorterte matrisen:

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;

Java Binary Search -ordningen fungerer på en liste som allerede er sortert.

Binære søkemetoder i Arrays -klassen

Ovennevnte utvalg av chars vil bli brukt i denne delen for illustrasjon. De binære søkemetodene er i Arrays -klassen til Java.util.* pakke. Denne pakken må importeres for at Arrays -klassen skal brukes.

Alle metodene i Arrays -klassen er statiske metoder. Dette betyr at et objekt ikke trenger å bli instantiert for noen av dets metoder som skal brukes. To av disse metodene er binære søkemetoder for chars. Syntaksen til en av de binære søkemetodene, for Chars er:

Public Static Int BinarySearch (Char [] A, Char Key)

Følgende program søker etter S som er funnet:

Importer Java.util.*;
public class theclass
public static void main (String [] args)
char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret = matriser.binarysearch (arr, 's');
System.ute.println (ret);

Utgangen er 6. Følgende kodesegment søker etter B, U og Z som ikke er funnet.

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret1 = matriser.binarysearch (arr, 'b');
int ret2 = matriser.binarysearch (arr, 'u');
int ret3 = matriser.binarysearch (arr, 'z');
System.ute.trykk (RET1); System.ute.print ("); system.ute.print (ret2);
System.ute.print ("); system.ute.print (ret3); System.ute.skrive ut(");
System.ute.println ();

Utgangen er,

-1 -9 -11

Søker etter et område

Syntaksen for å søke i en rekke rolle er:

public static int binarysearch (char [] a, int fromindex, int toindex, char nøkkel)

Fraindex er den normale indeksen som området starter. ToIndex er den normale indeksen like etter det siste elementet i området. Følgende kodesegment søker etter den sorterte matrisen som begynner fra indeks 3 til like etter indeks 7, som er indeks 8. Elementet for indeks 8 er ikke inkludert i området.

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret = matriser.BinarySearch (arr, 3, 8, 's');
System.ute.println (ret);

Nøkkelen er s, og utgangen er 6.

Konklusjon

Arrays -syntaksene for å søke i en rekke primitive typer er:

• public static int binarysearch (byte [] a, byte nøkkel)
• public static int binarysearch (byte [] a, int fromindex, int toindex, byte key)
• Public Static Int BinarySearch (Char [] A, Char Key)
• public static int binarysearch (char [] a, int fromindex, int toindex, char nøkkel)
• public static int binarysearch (double [] a, double nøkkel)
• public static int binarysearch (double [] a, int fromindex, int toindex, double nøkkel)
• public static int binarysearch (float [] a, float key)
• public static int binarysearch (float [] a, int fromindex, int toindex, float key)
• public static int binarysearch (int [] a, int nøkkel)
• offentlig statisk int binarysearch (int [] a, int fraindex, int toindex, int nøkkel)