Cos'è la ricerca binaria in Java? Come implementarlo?

La ricerca binaria in Java è un algoritmo di ricerca che trova la posizione di un valore di destinazione all'interno di un array ordinato. In questo articolo ti dirò come implementarlo con l'aiuto di un esempio.

Gli algoritmi di ricerca e ordinamento sono i file algoritmi popolari in qualsiasi linguaggio di programmazione. Sono la base per comprendere i fondamenti della programmazione. Uno di questi popolari algoritmi di ricerca è la ricerca binaria in . In questo articolo, ti parlerò della sua implementazione.

Gli argomenti seguenti sono trattati in questo articolo:





Iniziamo!

Cos'è la ricerca binaria?

Ricerca binaria in è un algoritmo di ricerca che trova la posizione di un valore target all'interno di un file ordinato Vettore . Ricerca binaria confronta il valore di destinazione con l'elemento centrale della matrice. Itfunziona solo su un insieme ordinato di elementi. Per utilizzare la ricerca binaria su una raccolta, il deve prima essere ordinato.



Programma di ricerca binaria in Java - Ricerca binaria in Java - EdurekaQuando il viene utilizzato per eseguire operazioni su un insieme ordinato, il numero di iterazioni può sempre essere ridotto in base al valore che si sta cercando. Puoi vedere nell'istantanea sopra di trovare il file elemento centrale . L'analogia della ricerca binaria consiste nell'utilizzare le informazioni a cui è ordinato l'array e ridurre la complessità temporale O (log n) .

Implementazione dell'algoritmo di ricerca binaria

Diamo un'occhiata allo pseudo codice sottostante per comprenderlo in modo migliore.

Procedura binary_search A & larr array ordinato n & larr dimensione dell'array x & larr valore da cercare Imposta basso = 1 Imposta alto = n mentre x non trovato se alto

Spiegazione:



Passo 1: Innanzitutto, confronta x con l'elemento centrale.

Passo 2: Se x corrisponde all'elemento centrale, devi restituire l'indice medio.

Passaggio 3: Altrimenti, se x è maggiore dell'elemento medio, allora x può trovarsi solo nel mezzo array del lato destro dopo l'elemento medio. Quindi ricorri la metà giusta.

Passaggio 4: Altrimenti, se (x è minore), ricorre per la metà sinistra.

È così che devi cercare l'elemento nell'array dato.

analizzare il file xml in java

Vediamo ora come implementare ricorsivamente un algoritmo di ricerca binaria. Di seguito il programma dimostra lo stesso.

Ricerca binaria ricorsiva

public class BinarySearch {// Implementazione Java della ricerca binaria ricorsiva // Restituisce l'indice di x se è presente in arr [l..h], altrimenti return -1 int binarySearch (int a [], int l, int h, int x) {if (h> = l) {int mid = l + (h - l) / 2 // Se l'elemento è presente al centro stesso if (a [mid] == x) return mid // If elemento è più piccolo di mid, quindi può essere presente solo nel sottoarray di sinistra se (a [mid]> x) return binarySearch (arr, l, mid - 1, x) // Altrimenti l'elemento può essere presente solo nel sottoarray di destra return binarySearch (arr, mid + 1, h, x)} // Raggiungiamo qui quando l'elemento non è presente nell'array return -1} public static void main (String args []) {BinarySearch ob = new BinarySearch () int a [] = {20, 30, 40, 10, 50} int n = a. Lunghezza int x = 40 int res = ob.binarySearch (a, 0, n - 1, x) if (res == -1) System.out .println ('Elemento non presente') else System.out.println ('Elemento trovato all'indice' + ris)}}

Eseguendo il programma di cui sopra, individuerà l'elemento presente nell'indice particolare

Elemento trovato all'indice 2

Quindi questo ci porta alla fine della ricerca binaria in Giava articolo. Spero che tu l'abbia trovato informativo e ti abbia aiutato a capire .

Controlla il da Edureka, una società di formazione online affidabile con una rete di oltre 250.000 studenti soddisfatti sparsi in tutto il mondo. Siamo qui per aiutarti in ogni fase del tuo viaggio, per diventare un oltre a queste domande dell'intervista Java. Realizziamo un curriculum progettato per studenti e professionisti che desiderano diventare sviluppatori Java. Il corso è progettato per darti un vantaggio nella programmazione Java e formarti per concetti Java sia di base che avanzati insieme a vari framework Java come Hibernate e Spring.

In caso di difficoltà durante l'implementazione della ricerca binaria in , per favore menzionalo nella sezione commenti qui sotto e ti risponderemo al più presto.