Array.binarySearch() Il metodo cerca nell'array specificato del tipo di dati specificato il valore specificato utilizzando l'algoritmo di ricerca binaria. L'array deve essere ordinato come da Array.sort() metodo prima di effettuare questa chiamata. Se non è ordinato, i risultati non sono definiti. Se l'array contiene più elementi con il valore specificato, non esiste alcuna garanzia su quale verrà trovato. Esaminiamo l'illustrazione fornita di seguito come segue.

Illustrazione:

Searching for 35 in byteArr[] = {10,20,15,22,35} will give result as 4 as it is the index of 35 Searching for g in charArr[] = {'g','p','q','c','i'} will give result as 0 as it is the index of 'g' Searching for 22 in intArr[] = {10,20,15,22,35}; will give result as 3 as it is the index of 22 Searching for 1.5 in doubleArr[] = {10.2,15.1,2.2,3.5} will give result as -1 as it is the insertion point of 1.5 Searching for 35.0 in floatArr[] = {10.2f,15.1f,2.2f,3.5f} will give result as -5 as it is the insertion point of 35.0 Searching for 5 in shortArr[] = {10,20,15,22,35} will give result as -1 as it is the insertion point of 5>

È il metodo più semplice ed efficiente per trovare un elemento in un array ordinato in Java

Sintassi:

public static int binarySearch(data_type arr, data_type key)>

Ricordare: Qui il tipo di dati può essere uno qualsiasi dei tipi di dati primitivi come byte, char, double, int, float, short, long e persino object.

parametri:

• L'array da cercare
• Il valore da cercare

Tipo di reso: indice della chiave di ricerca, se è contenuta nell'array; altrimenti, (-(punto di inserimento) – 1). Il punto di inserimento è definito come il punto in cui la chiave verrebbe inserita nell'array: l'indice del primo elemento maggiore della chiave o a.length se tutti gli elementi nell'array sono inferiori alla chiave specificata. Si noti che ciò garantisce che il valore restituito sarà>= 0 se e solo se la chiave viene trovata.

Ci sono alcuni punti importanti da tenere a mente come segue:

• Se l'elenco di input non è ordinato, i risultati non sono definiti.
• Se sono presenti duplicati, non vi è alcuna garanzia su quale verrà trovato.

Come sopra, abbiamo già discusso del fatto che possiamo utilizzare anche questo algoritmo Arrays.binarysearch() vs Collezioni.binarysearch() . Arrays.binarysearch() funziona anche per array che possono essere di tipo dati primitivo. Collezioni .binarysearch() funziona per raccolte di oggetti come Lista di array E Lista collegata .

Esempio 1:

Giava

ops in Java

>

>

35 found at index = 4 g found at index = 1 22 found at index = 3 1.5 found at index = -1 35.0 found at index = -5 5 found at index = -1>

Analisi della complessità:

Complessità temporale:
La complessità temporale del metodo Arrays.binarySearch() è O(log n) dove n è la lunghezza dell'array di input. Questo perché il metodo utilizza un algoritmo di ricerca binaria per trovare l'elemento di destinazione nell'array ordinato.

Spazio ausiliario:
Lo spazio ausiliario utilizzato dal metodo Arrays.binarySearch() è O(1) poiché non richiede spazio aggiuntivo oltre all'array di input per eseguire l'operazione di ricerca.

Esistono varianti di questo metodo in cui possiamo anche specificare l'intervallo di array in cui effettuare la ricerca. Ne discuteremo, oltre alla ricerca in un array di oggetti, in ulteriori post.

listnode java

Esempio 2:

Giava

convertire una stringa in intero

>

>

2>

Analisi della complessità:

Complessità temporale:
La complessità temporale del metodo BinarySearch() nella classe Collections è O(log n) dove n è il numero di elementi nell'elenco.

Spazio ausiliario:
Il metodo BinarySearch() nella classe Collections non richiede spazio aggiuntivo e quindi ha una complessità di spazio ausiliario pari a O(1).