binary search algorithm java implementation examples
Questo tutorial spiegherà la ricerca binaria e la ricerca binaria ricorsiva in Java insieme agli esempi di algoritmo, implementazione e codice di ricerca binario Java:
Una ricerca binaria in Java è una tecnica utilizzata per cercare un valore o una chiave mirati in una raccolta. È una tecnica che utilizza la tecnica del 'divide et impera' per cercare una chiave.
La raccolta su cui la ricerca binaria deve essere applicata per cercare una chiave deve essere ordinata in ordine crescente.
Di solito, la maggior parte dei linguaggi di programmazione supporta le tecniche di ricerca lineare, ricerca binaria e hash che vengono utilizzate per cercare i dati nella raccolta. Impareremo l'hashing nei nostri tutorial successivi.
=> Visita qui per imparare Java da zero.
Cosa imparerai:
Ricerca binaria in Java
La ricerca lineare è una tecnica di base. In questa tecnica, l'array viene attraversato in sequenza e ogni elemento viene confrontato con la chiave finché la chiave non viene trovata o viene raggiunta la fine dell'array.
La ricerca lineare è usata raramente nelle applicazioni pratiche. La ricerca binaria è la tecnica più utilizzata in quanto è molto più veloce di una ricerca lineare.
Java offre tre modi per eseguire una ricerca binaria:
domande e risposte dell'intervista di ms sql
- Utilizzando l'approccio iterativo
- Utilizzando un approccio ricorsivo
- Utilizzando il metodo Arrays.binarySearch ().
In questo tutorial, implementeremo e discuteremo tutti questi 3 metodi.
Algoritmo per la ricerca binaria in Java
Nel metodo di ricerca binaria, la raccolta viene ripetutamente divisa a metà e l'elemento chiave viene cercato nella metà sinistra o destra della raccolta, a seconda che la chiave sia minore o maggiore dell'elemento centrale della raccolta.
Un semplice algoritmo di ricerca binaria è il seguente:
- Calcola l'elemento medio della collezione.
- Confronta gli elementi chiave con l'elemento centrale.
- Se chiave = elemento centrale, restituiamo la posizione media dell'indice per la chiave trovata.
- Altrimenti Se chiave> elemento medio, la chiave si trova nella metà destra della raccolta. Quindi ripetere i passaggi da 1 a 3 nella metà inferiore (destra) della raccolta.
- Altra chiave
Come puoi vedere dai passaggi precedenti, nella ricerca binaria, metà degli elementi nella raccolta vengono ignorati subito dopo il primo confronto.
Si noti che la stessa sequenza di passaggi vale per la ricerca binaria iterativa e ricorsiva.
Illustriamo l'algoritmo di ricerca binaria utilizzando un esempio.
Per esempio, prendi il seguente array ordinato di 10 elementi.
Calcoliamo la posizione centrale dell'array.
Medio = 0 + 9/2 = 4
# 1) Chiave = 21
Innanzitutto, confronteremo il valore della chiave con l'elemento (mid) e scopriremo che il valore dell'elemento a metà = 21.
Quindi troviamo quella chiave = (metà). Quindi la chiave si trova nella posizione 4 nella matrice.
# 2) Chiave = 25
Per prima cosa confrontiamo il valore della chiave con mid. As (21<25), we will directly search for the key in the upper half of the array.
Ora troveremo di nuovo la metà per la metà superiore dell'array.
Medio = 4 + 9/2 = 6
Il valore nella posizione (metà) = 25
Ora confrontiamo l'elemento chiave con l'elemento medio. Quindi (25 == 25), quindi abbiamo trovato la chiave nella posizione (metà) = 6.
i migliori server su cui giocare wow
Quindi dividiamo ripetutamente l'array e confrontando l'elemento chiave con il centro, decidiamo in quale metà cercare la chiave. La ricerca binaria è più efficiente in termini di tempo e correttezza ed è anche molto più veloce.
Implementazione della ricerca binaria Java
Utilizzando l'algoritmo di cui sopra, implementiamo un programma di ricerca binaria in Java utilizzando l'approccio iterativo. In questo programma, prendiamo un array di esempio ed eseguiamo una ricerca binaria su questo 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!'); } } } Produzione:
La matrice di input: (5, 10, 15, 20, 25, 30, 35)
Chiave da cercare = 20
L'elemento si trova all'indice: 3
Il programma sopra mostra un approccio iterativo della ricerca binaria. Inizialmente, viene dichiarato un array, quindi viene definita una chiave da cercare.
Dopo aver calcolato la metà dell'array, la chiave viene confrontata con l'elemento medio. Quindi, a seconda che la chiave sia minore o maggiore della chiave, la chiave viene cercata rispettivamente nella metà inferiore o superiore della matrice.
Ricerca binaria ricorsiva in Java
È inoltre possibile eseguire una ricerca binaria utilizzando la tecnica della ricorsione. Qui, il metodo di ricerca binaria viene chiamato in modo ricorsivo fino a quando la chiave non viene trovata o l'intero elenco è esaurito.
Di seguito viene fornito il programma che implementa una ricerca binaria ricorsiva:
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'); } } Produzione:
Elenco di input: (1, 11, 21, 31, 41, 51, 61, 71, 81, 91
La chiave da cercare:
La chiave si trova nella posizione: 3 nell'elenco
Utilizzando il metodo Arrays.binarySearch ().
La classe Arrays in Java fornisce un metodo 'binarySearch ()' che esegue la ricerca binaria sull'array specificato. Questo metodo accetta l'array e la chiave da cercare come argomenti e restituisce la posizione della chiave nell'array. Se la chiave non viene trovata, il metodo restituisce -1.
L'esempio seguente implementa il metodo 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.'); } } Produzione:
La matrice di input: (10, 20, 30, 40, 50, 60, 70, 80, 90)
La chiave da cercare: 50
La chiave si trova all'indice: 4 nell'array.
Domande frequenti
D # 1) Come scrivi una ricerca binaria?
Risposta: La ricerca binaria viene solitamente eseguita dividendo l'array in due metà. Se la chiave da cercare è maggiore dell'elemento medio, viene cercata la metà superiore dell'array dividendo ulteriormente e cercando il sotto-array fino a trovare la chiave.
Allo stesso modo, se la chiave è minore dell'elemento medio, la chiave viene cercata nella metà inferiore dell'array.
D # 2) Dove viene utilizzata la ricerca binaria?
Risposta: La ricerca binaria viene utilizzata principalmente per cercare dati ordinati nelle applicazioni software, soprattutto quando lo spazio di memoria è compatto e limitato.
D # 3) Qual è la O grande della ricerca binaria?
Risposta: La complessità temporale della ricerca binaria è O (logn) dove n è il numero di elementi nell'array. La complessità spaziale della ricerca binaria è O (1).
D # 4) La ricerca binaria è ricorsiva?
Risposta: Sì. Poiché la ricerca binaria è un esempio di strategia divide et impera e può essere implementata utilizzando la ricorsione. Possiamo dividere l'array in metà e chiamare lo stesso metodo per eseguire la ricerca binaria ancora e ancora.
come eseguire un oggetto flash Shockwave
D # 5) Perché si chiama ricerca binaria?
Risposta: L'algoritmo di ricerca binaria utilizza una strategia divide et impera che taglia ripetutamente l'array in metà o due parti. Quindi è chiamato come ricerca binaria.
Conclusione
La ricerca binaria è la tecnica di ricerca utilizzata di frequente in Java. Il requisito per eseguire una ricerca binaria è che i dati siano ordinati in ordine crescente.
Una ricerca binaria può essere implementata utilizzando un approccio iterativo o ricorsivo. La classe Arrays in Java fornisce anche il metodo 'binarySearch' che esegue una ricerca binaria su un array.
Nelle nostre esercitazioni successive, esploreremo varie tecniche di ordinamento in Java.
=> Guarda qui la serie di formazione su Java semplice.
Lettura consigliata
- Ordina selezione in Java - Algoritmo di ordinamento selezione ed esempi
- Ordinamento di inserimento in Java - Algoritmo ed esempi di ordinamento di inserimento
- Albero di ricerca binario C ++: implementazione BST e operazioni con esempi
- Tutorial sull'interfaccia Java e sulla classe astratta con esempi
- Tutorial JAVA per principianti: oltre 100 tutorial video Java pratici
- Bubble Sort in Java - Algoritmi di ordinamento Java ed esempi di codice
- Tutorial Java String | Metodi Java String con esempi
- Cos'è Java Vector | Tutorial Java Vector Class con esempi