binary search algorithm java implementation examples
Denna handledning kommer att förklara binär sökning och rekursiv binär sökning i Java tillsammans med dess exempel på algoritm, implementering och Java binär sökkod:
En binär sökning i Java är en teknik som används för att söka efter ett riktat värde eller nyckel i en samling. Det är en teknik som använder 'dela och erövra' -tekniken för att söka efter en nyckel.
Samlingen som Binär sökning ska användas för att söka efter en nyckel måste sorteras i stigande ordning.
Vanligtvis stöder de flesta programmeringsspråken linjär sökning, binär sökning och hashteknik som används för att söka efter data i samlingen. Vi lär oss hashing i våra efterföljande handledning.
=> Besök här för att lära dig Java från Scratch.
Vad du kommer att lära dig:
Binär sökning i Java
Linjär sökning är en grundläggande teknik. I denna teknik passeras matrisen sekventiellt och varje element jämförs med nyckeln tills nyckeln hittas eller slutet på matrisen nås.
Linjär sökning används sällan i praktiska tillämpningar. Binär sökning är den mest använda tekniken eftersom den är mycket snabbare än en linjär sökning.
Java erbjuder tre sätt att utföra en binär sökning:
vad är black box-test med exempel
- Med hjälp av den iterativa metoden
- Med ett rekursivt tillvägagångssätt
- Med hjälp av metoden Arrays.binarySearch ().
I denna handledning kommer vi att implementera och diskutera alla dessa 3 metoder.
Algoritm för binär sökning i Java
I den binära sökmetoden delas samlingen upprepade gånger i hälften och nyckelelementet söks i den vänstra eller högra halvan av samlingen beroende på om nyckeln är mindre än eller större än mittelementet i samlingen.
En enkel binär sökalgoritm är som följer:
- Beräkna mittelementet i samlingen.
- Jämför nyckelobjekten med mittelementet.
- Om nyckel = mittelement returnerar vi mittindexpositionen för den hittade nyckeln.
- Annars om nyckel> mittelement, ligger nyckeln i den högra halvan av samlingen. Upprepa sålunda steg 1 till 3 på den nedre (högra) halvan av samlingen.
- Annan nyckel
Som du kan se från ovanstående steg ignoreras halva elementen i samlingen i binär sökning strax efter den första jämförelsen.
Observera att samma sekvens av steg gäller för både iterativ och rekursiv binär sökning.
Låt oss illustrera den binära sökalgoritmen med ett exempel.
Till exempel, ta följande sorterade matris med 10 element.
Låt oss beräkna matrisens mittposition.
Mitt = 0 + 9/2 = 4
# 1) Nyckel = 21
Först ska vi jämföra nyckelvärdet med [mitt] -elementet och vi finner att elementvärdet vid mitten = 21.
Således hittar vi den nyckeln = [mitt]. Följaktligen finns nyckeln vid position 4 i matrisen.
# 2) Nyckel = 25
bredd första sökalgoritmen c ++
Vi jämför först nyckelvärdet med mitten. Som (21<25), we will directly search for the key in the upper half of the array.
Nu åter hittar vi mitten för den övre halvan av matrisen.
Mitt = 4 + 9/2 = 6
Värdet på plats [mitten] = 25
Nu jämför vi nyckelelementet med mittelementet. Så (25 == 25), därför har vi hittat nyckeln på plats [mitt] = 6.
Således delar vi upprepade gånger arrayen och genom att jämföra nyckelelementet med mitten bestämmer vi i vilken hälft vi ska söka efter nyckeln. Binär sökning är effektivare när det gäller tid och korrekthet och är också mycket snabbare.
Binär sökimplementering Java
Med hjälp av ovanstående algoritm, låt oss implementera ett binärt sökprogram i Java med hjälp av iterativt tillvägagångssätt. I det här programmet tar vi ett exempel på en array och utför binär sökning på denna 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:
Inmatningsmatrisen: [5, 10, 15, 20, 25, 30, 35]
Nyckel som ska sökas = 20
Element finns i index: 3
Ovanstående program visar en iterativ metod för binär sökning. Inledningsvis deklareras en matris och sedan definieras en nyckel som ska sökas.
Efter beräkning av mitten av matrisen jämförs nyckeln med mittelementet. Beroende på om nyckeln är mindre än eller större än nyckeln, söks nyckeln i den nedre respektive övre halvan av matrisen.
Rekursiv binär sökning i Java
Du kan också utföra en binär sökning med rekursionstekniken. Här kallas den binära sökmetoden rekursivt tills nyckeln hittas eller hela listan är uttömd.
Programmet som implementerar en rekursiv binär sökning ges nedan:
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:
mobiltelefon spion appar för Android
Ingångslista: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91
Nyckeln som ska sökas:
Nyckeln finns på plats: 3 i listan
Med hjälp av metoden Arrays.binarySearch ().
Arrays-klassen i Java tillhandahåller en 'binarySearch ()' -metod som utför binärsökning på den angivna matrisen. Denna metod tar matrisen och nyckeln som ska sökas som argument och returnerar nyckelns position i matrisen. Om nyckeln inte hittas returnerar metoden -1.
Nedanstående exempel implementerar 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:
Inmatningsmatrisen: [10, 20, 30, 40, 50, 60, 70, 80, 90]
Nyckeln som ska sökas: 50
Nyckeln finns i index: 4 i matrisen.
Vanliga frågor
F # 1) Hur skriver du en binär sökning?
Svar: Binär sökning utförs vanligtvis genom att dela upp matrisen i halvor. Om nyckeln som ska sökas är större än mittelementet, söks den övre halvan av matrisen genom att ytterligare dela och söka i undergruppen tills nyckeln hittas.
På samma sätt, om nyckeln är mindre än mittelementet, söks nyckeln i den nedre halvan av matrisen.
F # 2) Var används den binära sökningen?
Svar: Binär sökning används främst för att söka efter sorterad data i programvaruapplikationer, särskilt när minnesutrymmet är kompakt och begränsat.
F # 3) Vad är den stora O för binär sökning?
Svar: Tidskomplexiteten för den binära sökningen är O (logn) där n är antalet element i matrisen. Rymdkomplexiteten för den binära sökningen är O (1).
F # 4) Är binär sökning rekursiv?
Svar: Ja. Eftersom binär sökning är ett exempel på en divide-and-conquer-strategi och den kan implementeras med rekursion. Vi kan dela upp matrisen i halvor och kalla samma metod för att utföra den binära sökningen om och om igen.
F # 5) Varför kallas det en binär sökning?
Svar: Den binära sökalgoritmen använder en delnings- och erövringsstrategi som upprepade gånger skär upp matrisen i halvor eller två delar. Således heter det som binär sökning.
Slutsats
Binär sökning är den ofta använda söktekniken i Java. Kravet på att en binär sökning ska utföras är att data ska sorteras i stigande ordning.
En binär sökning kan implementeras antingen med hjälp av en iterativ eller rekursiv metod. Arrays-klass i Java tillhandahåller också metoden 'binarySearch' som utför en binär sökning på en matris.
I våra efterföljande handledning kommer vi att utforska olika sorteringstekniker i Java.
=> Se upp den enkla Java-träningsserien här.
Rekommenderad läsning
- Selection Sort In Java - Selection Sort Algorithm & Exempel
- Insertion Sort In Java - Insertion Sort Algorithm & Exempel
- Binärt sökträd C ++: BST-implementering och operationer med exempel
- Java-gränssnitt och abstrakt klasshandledning med exempel
- JAVA-handledning för nybörjare: 100+ praktiska Java-videohandledning
- Bubblesortering i Java - Java-sorteringsalgoritmer och kodexempel
- Java String Tutorial | Java-strängmetoder med exempel
- Vad är Java Vector | Java Vector Class Tutorial med exempel