Meny

Binær søkealgoritme i Java - implementering og eksempler

  • Hoved
  • Annen
  • Binær søkealgoritme i Java - implementering og eksempler

binary search algorithm java implementation examples

Prøv Instrumentet Vårt For Å Eliminere Problemer

Denne opplæringen vil forklare Binary Search & Recursive Binary Search i Java sammen med algoritme, implementering og Java Binary Seach Code eksempler:

Et binært søk i Java er en teknikk som brukes til å søke etter en målrettet verdi eller nøkkel i en samling. Det er en teknikk som bruker 'del og erobre' teknikken for å søke etter en nøkkel.

Samlingen som binært søk skal brukes på for å søke etter en nøkkel, må sorteres i stigende rekkefølge.

Vanligvis støtter de fleste programmeringsspråkene Lineær søk, Binær søk og Hashing-teknikker som brukes til å søke etter data i samlingen. Vi lærer hashing i de påfølgende opplæringene våre.

=> Besøk her for å lære Java fra bunnen av.

Binært søk i Java

Hva du vil lære:

Binært søk i Java

Lineært søk er en grunnleggende teknikk. I denne teknikken krysses matrisen sekvensielt, og hvert element sammenlignes med nøkkelen til nøkkelen er funnet eller enden på matrisen er nådd.

Lineært søk brukes sjelden i praktiske anvendelser. Binært søk er den mest brukte teknikken, da det er mye raskere enn et lineært søk.

Java gir tre måter å utføre et binært søk på:

beste gratis datarenser og reparasjon
  1. Ved hjelp av iterativ tilnærming
  2. Ved hjelp av en rekursiv tilnærming
  3. Ved hjelp av Arrays.binarySearch () -metoden.

I denne opplæringen vil vi implementere og diskutere alle disse 3 metodene.

Algoritme for binær søk i Java

I den binære søkemetoden deles samlingen gjentatte ganger i halvparten, og nøkkelelementet blir søkt i venstre eller høyre halvdel av samlingen, avhengig av om nøkkelen er mindre enn eller større enn midtelementet i samlingen.

En enkel binær søkealgoritme er som følger:

  1. Beregn midtelementet i samlingen.
  2. Sammenlign nøkkelelementene med midtelementet.
  3. Hvis nøkkel = midtelement, returnerer vi midtindeksposisjonen for nøkkelen som ble funnet.
  4. Ellers hvis nøkkel> midtelement, så ligger nøkkelen i høyre halvdel av samlingen. Gjenta således trinn 1 til 3 på den nedre (høyre) halvdelen av samlingen.
  5. Annen nøkkel

Som du kan se fra trinnene ovenfor, i binært søk, blir halvparten av elementene i samlingen ignorert like etter den første sammenligningen.

Vær oppmerksom på at den samme trinnsekvensen gjelder både iterativ og rekursiv binærsøk.

La oss illustrere den binære søkealgoritmen ved hjelp av et eksempel.

For eksempel, ta følgende sorterte utvalg med 10 elementer.

Sortert utvalg med 10 elementer

La oss beregne den midtre plasseringen av matrisen.

Midt = 0 + 9/2 = 4

midtre plassering av matrisen

# 1) Nøkkel = 21

Først skal vi sammenligne nøkkelverdien med (midt) -elementet, og vi finner ut at elementverdien midt = 21.

dijkstras algoritme som bruker prioritetskø java

Nøkkel = 21

Dermed finner vi den nøkkelen = (midt). Derfor er nøkkelen funnet på posisjon 4 i matrisen.

# 2) Nøkkel = 25

Nøkkel = 25

Vi sammenligner først nøkkelverdien med midten. Som (21<25), we will directly search for the key in the upper half of the array.

søk etter nøkkelen i øvre halvdel av matrisen.

Nå vil vi igjen finne midten for den øvre halvdelen av matrisen.

Midt = 4 + 9/2 = 6

Verdien på stedet (midt) = 25

verdi på plassering (midt) = 25

Nå sammenligner vi nøkkelelementet med midtelementet. Så (25 == 25), derfor har vi funnet nøkkelen på plassering (midt) = 6.

Dermed deler vi matrisen gjentatte ganger, og ved å sammenligne nøkkelelementet med midten bestemmer vi i hvilken halvdel vi skal søke etter nøkkelen. Binært søk er mer effektivt når det gjelder tid og korrekthet og er mye raskere også.

Binær søkimplementering Java

La oss bruke algoritmen ovenfor, implementere et binært søkeprogram i Java ved hjelp av iterativ tilnærming. I dette programmet tar vi et eksempel på en rekke og utfører binært søk på denne matrisen.

import java.util.*; class Main{ public static void main(String args()){ int numArray() = {5,10,15,20,25,30,35}; System.out.println('The input array: ' + Arrays.toString(numArray)); //key to be searched int key = 20; System.out.println(' Key to be searched=' + key); //set first to first index int first = 0; //set last to last elements in array int last=numArray.length-1; //calculate mid of the array int mid = (first + last)/2; //while first and last do not overlap while( first <= last ){ //if the mid < key, then key to be searched is in the first half of array if ( numArray(mid) last ){ System.out.println('Element is not found!'); } } }

Produksjon:

Inndatamatrisen: (5, 10, 15, 20, 25, 30, 35)
Nøkkel som skal søkes = 20
Element er funnet ved indeks: 3

Output - implementering av binær søk java

Ovennevnte program viser en iterativ tilnærming til binær søk. Opprinnelig erklæres en matrise, og deretter defineres en nøkkel som skal søkes.

Etter å ha beregnet midten av matrisen, blir nøkkelen sammenlignet med midtelementet. Avhengig av om nøkkelen er mindre enn eller større enn nøkkelen, blir det søkt i henholdsvis nedre eller øvre halvdel av matrisen.

Rekursivt binært søk i Java

Du kan også utføre et binært søk ved hjelp av rekursjonsteknikken. Her kalles den binære søkemetoden rekursivt til nøkkelen er funnet eller hele listen er oppbrukt.

Programmet som implementerer et rekursivt binært søk er gitt nedenfor:

import java.util.*; class Main{ //recursive method for binary search public static int binary_Search(int intArray(), int low, int high, int key){ //if array is in order then perform binary search on the array if (high>=low){ //calculate mid int mid = low + (high - low)/2; //if key =intArray(mid) return mid if (intArray(mid) == key){ return mid; } //if intArray(mid) > key then key is in left half of array if (intArray(mid) > key){ return binary_Search(intArray, low, mid-1, key);//recursively search for key }else //key is in right half of the array { return binary_Search(intArray, mid+1, high, key);//recursively search for key } } return -1; } public static void main(String args()){ //define array and key int intArray() = {1,11,21,31,41,51,61,71,81,91}; System.out.println('Input List: ' + Arrays.toString(intArray)); int key = 31; System.out.println(' The key to be searched:' + key); int high=intArray.length-1; //call binary search method int result = binary_Search(intArray,0,high,key); //print the result if (result == -1) System.out.println(' Key not found in given list!'); else System.out.println(' Key is found at location: '+result + ' in the list'); } }

Produksjon:

Inngangsliste: (1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Nøkkelen som skal søkes:
Nøkkelen finnes på stedet: 3 i listen

Output - Rekursivt binært søk i Java

Ved hjelp av Arrays.binarySearch () -metoden.

Arrays-klassen i Java gir en 'binarySearch ()' -metode som utfører binært søk på den gitte matrisen. Denne metoden tar matrisen og nøkkelen som skal søkes som argumenter og returnerer posisjonen til nøkkelen i matrisen. Hvis nøkkelen ikke blir funnet, returnerer metoden -1.

Eksemplet nedenfor implementerer metoden Arrays.binarySearch ().

import java.util.Arrays; class Main{ public static void main(String args()){ //define an array int intArray() = {10,20,30,40,50,60,70,80,90}; System.out.println('The input Array : ' + Arrays.toString(intArray)); //define the key to be searched int key = 50; System.out.println(' The key to be searched:' + key); //call binarySearch method on the given array with key to be searched int result = Arrays.binarySearch(intArray,key); //print the return result if (result <0) System.out.println(' Key is not found in the array!'); else System.out.println(' Key is found at index: '+result + ' in the array.'); } }

Produksjon:

Input Array: (10, 20, 30, 40, 50, 60, 70, 80, 90)
Nøkkelen som skal søkes: 50
Nøkkelen finnes ved indeks: 4 i matrisen.

Output - Bruk metoden Arrays.binarySearch ().

ofte stilte spørsmål

Sp # 1) Hvordan skriver du et binært søk?

Svar: Binært søk utføres vanligvis ved å dele matrisen i halvdeler. Hvis nøkkelen som skal søkes er større enn midtelementet, blir den øvre halvdelen av matrisen søkt ved å dele og søke i underruten til nøkkelen blir funnet.

På samme måte, hvis nøkkelen er mindre enn midtelementet, blir det søkt på nøkkelen i den nedre halvdelen av matrisen.

Q # 2) Hvor brukes binært søk?

Svar: Binært søk brukes hovedsakelig til å søke etter sorterte data i programvareapplikasjoner, spesielt når minneplassen er kompakt og begrenset.

Q # 3) Hva er den store O av binært søk?

Svar: Tidskompleksiteten til det binære søket er O (logn) hvor n er antall elementer i matrisen. Romkompleksiteten til det binære søket er O (1).

Q # 4) Er binært søk rekursivt?

Svar: Ja. Siden binært søk er et eksempel på en splitt-og-erobre-strategi, og den kan implementeres ved hjelp av rekursjon. Vi kan dele matrisen i halvdeler og kalle den samme metoden for å utføre det binære søket igjen og igjen.

Q # 5) Hvorfor kalles det et binært søk?

mobiltelefon spion apper for android

Svar: Den binære søkealgoritmen bruker en delings- og erobringsstrategi som gjentatte ganger kutter matrisen i halvdeler eller to deler. Dermed blir den navngitt som binært søk.

Konklusjon

Binært søk er den ofte brukte søketeknikken i Java. Kravet om at et binært søk skal utføres er at dataene skal sorteres i stigende rekkefølge.

Et binært søk kan implementeres enten ved hjelp av en iterativ eller rekursiv tilnærming. Arrays-klasse i Java gir også ‘binarySearch’-metoden som utfører et binært søk på en matrise.

I de påfølgende opplæringene vil vi utforske ulike sorteringsteknikker i Java.

=> Se opp den enkle Java-treningsserien her.

Anbefalt lesing

^