Menu

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

  • Vigtigste
  • Andet
  • Binær søgealgoritme i Java - implementering og eksempler

binary search algorithm java implementation examples

Prøv Vores Instrument Til At Fjerne Problemer

Denne vejledning forklarer binær søgning og rekursiv binær søgning i Java sammen med dens eksempler på algoritme, implementering og Java binær søgeord:

En binær søgning i Java er en teknik, der bruges til at søge efter en målrettet værdi eller nøgle i en samling. Det er en teknik, der bruger 'opdele og erobre' teknikken til at søge efter en nøgle.

Samlingen, som binær søgning skal anvendes til at søge efter en nøgle, skal sorteres i stigende rækkefølge.

Normalt understøtter de fleste programmeringssprog lineær søgning, binær søgning og hashteknikker, der bruges til at søge efter data i samlingen. Vi lærer hashing i vores efterfølgende tutorials.

=> Besøg her for at lære Java fra bunden.

Binær søgning i Java

Hvad du vil lære:

Binær søgning i Java

Lineær søgning er en grundlæggende teknik. I denne teknik krydses arrayet sekventielt, og hvert element sammenlignes med nøglen, indtil nøglen er fundet, eller slutningen af ​​arrayet er nået.

Lineær søgning bruges sjældent i praktiske anvendelser. Binær søgning er den mest anvendte teknik, da den er meget hurtigere end en lineær søgning.

Java giver tre måder at udføre en binær søgning på:

er netværkssikkerhedsnøgle samme som adgangskode
  1. Brug af iterativ tilgang
  2. Ved hjælp af en rekursiv tilgang
  3. Brug af Arrays.binarySearch () -metoden.

I denne vejledning implementerer og diskuterer vi alle disse 3 metoder.

Algoritme til binær søgning i Java

I den binære søgemetode opdeles samlingen gentagne gange i halvdelen, og nøgleelementet søges i venstre eller højre halvdel af samlingen, afhængigt af om nøglen er mindre end eller større end midtelementet i samlingen.

En simpel binær søgealgoritme er som følger:

  1. Beregn samlingens midterste element.
  2. Sammenlign nøgleelementerne med mellemelementet.
  3. Hvis nøgle = midterelement, returnerer vi midtindekspositionen for den fundet nøgle.
  4. Ellers hvis nøgle> midtelement, så ligger nøglen i højre halvdel af samlingen. Gentag således trin 1 til 3 på den nederste (højre) halvdel af samlingen.
  5. Else nøgle

Som du kan se fra ovenstående trin ignoreres halvdelen af ​​elementerne i samlingen i binær søgning lige efter den første sammenligning.

Bemærk, at den samme sekvens af trin gælder for iterativ såvel som rekursiv binær søgning.

Lad os illustrere den binære søgealgoritme ved hjælp af et eksempel.

For eksempel, tag følgende sorterede matrix med 10 elementer.

Sorteret matrix med 10 elementer

Lad os beregne arrayets midterste placering.

Mid = 0 + 9/2 = 4

den midterste placering af arrayet

# 1) Tast = 21

Først sammenligner vi nøgleværdien med (mid) -elementet, og vi finder ud af, at elementværdien midt = 21.

Nøgle = 21

Således finder vi den nøgle = (mid). Derfor findes nøglen i position 4 i arrayet.

# 2) Tast = 25

Nøgle = 25

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

søg efter nøglen i den øverste halvdel af arrayet.

Nu igen finder vi midten til den øverste halvdel af arrayet.

er der et vr-headset til xbox one

Midt = 4 + 9/2 = 6

Værdien på placering (midt) = 25

værdi på placering (midt) = 25

Nu sammenligner vi nøgleelementet med mellemelementet. Så (25 == 25), derfor har vi fundet nøglen på placering (mid) = 6.

Således deler vi arrayet gentagne gange, og ved at sammenligne nøgleelementet med midten beslutter vi, i hvilken halvdel vi vil søge efter nøglen. Binær søgning er mere effektiv med hensyn til tid og korrekthed og er også meget hurtigere.

Implementering af binær søgning Java

Brug ovenstående algoritme til at implementere et binært søgeprogram i Java ved hjælp af iterativ tilgang. I dette program tager vi et eksempel på array og udfører binær søgning på dette array.

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!'); } } }

Produktion:

Input array: (5, 10, 15, 20, 25, 30, 35)
Nøgle, der skal søges = 20
Element findes ved indeks: 3

Output - implementering af binær søgning java

Ovenstående program viser en iterativ tilgang til binær søgning. Oprindeligt erklæres en matrix, hvorefter en nøgle, der skal søges, defineres.

Efter beregning af midten af ​​arrayet sammenlignes nøglen med midterelementet. Afhængigt af om nøglen er mindre end eller større end nøglen, søges der derefter på nøglen i henholdsvis den nedre eller øverste halvdel af arrayet.

Rekursiv binær søgning i Java

Du kan også udføre en binær søgning ved hjælp af rekursionsteknikken. Her kaldes den binære søgemetode rekursivt, indtil nøglen findes, eller hele listen er opbrugt.

Programmet, der implementerer en rekursiv binær søgning, er angivet 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'); } }

Produktion:

Inputliste: (1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Nøglen, der skal søges:
Nøglen findes på stedet: 3 på listen

Output - Rekursiv binær søgning i Java

Brug af Arrays.binarySearch () -metoden.

Arrays-klassen i Java giver en 'binærsøgning ()' - metode, der udfører binær søgning på den givne matrix. Denne metode tager arrayet og nøglen, der skal søges som argumenter, og returnerer nøglens position i arrayet. Hvis nøglen ikke findes, returnerer metoden -1.

Nedenstående eksempel 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.'); } }

Produktion:

Input Array: (10, 20, 30, 40, 50, 60, 70, 80, 90)
Nøglen, der skal søges: 50
Nøglen findes ved indeks: 4 i arrayet.

Output - Brug Arrays.binarySearch () -metoden.

Ofte stillede spørgsmål

Q # 1) Hvordan skriver du en binær søgning?

hvordan spiller du mkv-filer

Svar: Binær søgning udføres normalt ved at opdele arrayet i halvdele. Hvis den nøgle, der skal søges, er større end midterelementet, søges den øverste halvdel af arrayet ved yderligere at opdele og søge i underarrayet, indtil nøglen findes.

Tilsvarende, hvis nøglen er mindre end midtelementet, søges der på nøglen i den nedre halvdel af arrayet.

Q # 2) Hvor anvendes den binære søgning?

Svar: Binær søgning bruges hovedsageligt til at søge efter sorterede data i softwareapplikationer, især når hukommelsespladsen er kompakt og begrænset.

Q # 3) Hvad er den store O ved binær søgning?

Svar: Tidskompleksiteten af ​​den binære søgning er O (logn) hvor n er antallet af elementer i arrayet. Rumkompleksiteten af ​​den binære søgning er O (1).

Q # 4) Er binær søgning rekursiv?

Svar: Ja. Da binær søgning er et eksempel på en divide-and-conquer-strategi, og den kan implementeres ved hjælp af rekursion. Vi kan dele arrayet i halvdele og kalde den samme metode til at udføre den binære søgning igen og igen.

Q # 5) Hvorfor kaldes det en binær søgning?

Svar: Den binære søgealgoritme bruger en divide-and-conquer-strategi, der gentagne gange skærer arrayet i halvdele eller to dele. Således er det navngivet som binær søgning.

Konklusion

Binær søgning er den ofte anvendte søgeteknik i Java. Kravet om, at der skal udføres en binær søgning, er at dataene sorteres i stigende rækkefølge.

En binær søgning kan implementeres enten ved hjælp af en iterativ eller rekursiv tilgang. Arrays-klasse i Java leverer også metoden 'binærsøgning', der udfører en binær søgning på en matrix.

I vores efterfølgende tutorials vil vi udforske forskellige sorteringsteknikker i Java.

=> Hold øje med den enkle Java-træningsserie her.

Anbefalet læsning

^