Ricerca binaria in Java

La ricerca di un array per la posizione di un valore e l'ordinamento dell'array, sono due processi diversi. La ricerca significa verificare se si trova un valore chiamato chiave. L'ordinamento significa mettere tutti i valori nell'array in un ordine particolare (ascendente o discendente). Se un array non è ordinato ed è richiesta la ricerca, il programma deve iniziare dall'indice zero, quindi all'indice 1, quindi indice 2 e così via, fino a quando non raggiunge l'indice del valore che sta cercando. Se il valore si verifica più di una volta, il primo indice deve essere restituito.

Se l'array viene ordinato per primo, diciamo in ordine crescente, allora la ricerca diventa facile. L'indice è inferiore all'indice per l'elemento medio, se la chiave è inferiore al valore dell'indice medio o l'indice è uguale o maggiore di quello dell'indice medio, se il valore è uguale o maggiore quello del valore dell'indice medio.

Quindi dividi l'array in due. Se il valore si trova sul lato sinistro, non è necessario perdere tempo a cercare sul lato destro; Basta cercare sul lato sinistro. Se il valore si trova sul lato destro, non è necessario perdere tempo a cercare sul lato sinistro; Basta cercare sul lato destro. Poiché l'array è già completamente ordinato, quando entrambi i lati sono arrivati, è di nuovo diviso in due e viene cercata solo una delle nuove coppie di lati. In effetti, la ricerca in questo modo è semplicemente divisa in due, fino a quando l'indice del valore non viene raggiunto. Nessuna ricerca effettiva in termini di scansione ha luogo perché l'array è già ordinato. Potrebbe esserci un leggero movimento a destra e qualche leggero muoversi a sinistra nell'array durante la ricerca.

Binario implica, due. E quindi questo tipo di ricerca si chiama ricerca binaria. Esistono diversi ordini di ordinamento: tutti i valori nell'array possono essere ordinati in ordine crescente o in ordine decrescente completamente. Un array può anche essere ordinato in quello che è noto come formato di albero di ricerca binaria. Questo non è un ordinamento completo in ordine crescente o discendente. Tuttavia, la ricerca dell'algoritmo binario funziona ancora con questo formato.

Questo articolo spiega la ricerca binaria di Java. L'algoritmo di ricerca binaria in Java funziona su un array già ordinato. In questo articolo è considerato solo l'ordinamento completo in ordine crescente. Questo articolo inizia con illustrazione dell'algoritmo di ricerca binaria. Quindi continua a spiegare come utilizzare i metodi binarysearch () della classe Java Arrays.

Contenuto dell'articolo

• Illustrazione dell'algoritmo di ricerca binaria
• Pacchetto Java e classe per la ricerca binaria
• Costruire l'array per la ricerca
• Metodi di ricerca binaria della classe Arrays
• Ricerca di un intervallo
• Conclusione

Illustrazione dell'algoritmo di ricerca binaria

Considera la seguente sequenza di caratteri:

P V D Q S X T H N O

Organizzando in ordine crescente, la sequenza diventa:

D h n o p q s t v x

Ci sono dieci elementi qui. Il conteggio dell'indice inizia da 0. Quando il numero di elementi è pari (E.G., 10), l'indice per l'elemento medio è considerato come il numero di elementi divisi per due. In questo caso, 10/2 è 5. Quando il numero di elementi è dispari, l'indice per l'elemento medio viene preso come parte intera (numero intero) del numero di elementi diviso per due.

Ci sono due elenchi sopra. Il secondo è la forma ordinata della prima. Supponiamo che la ricerca fosse di sapere se S fosse presente nel primo elenco. L'elenco dovrebbe prima essere ordinato per avere il secondo elenco nello schema di ricerca binaria. Nell'elenco ordinato, l'indice per la posizione centrale è 5 = 10/2. Questo corrisponde al valore, q. La ricerca si interrompe quindi per verificare se Q è s, il valore cercava. Se lo è, la ricerca si interrompe. In caso contrario, la ricerca controlla se s si trova meno di q o da q verso l'alto.

In questo caso, si trova nell'intervallo da Q verso l'alto, che viene poi scelto. Non verrà sprecato il tempo per cercare nella metà inferiore dell'elenco (array). Quindi, questa nuova gamma deve essere divisa in due. Questa gamma è composta da 5 elementi. 5/2 = 2 e un 1/2. L'elemento centrale è nella posizione 2 di questa nuova gamma. Ciò corrisponde a t, se il conteggio da zero deve iniziare da q. L'indice effettivo di T è 7.

L'intervallo inferiore o sinistro ora è costituito da (q s), mentre la nuova gamma superiore o destra ora è costituita da (t v x). È il nuovo elemento medio, t uguale a s, il valore cercato? - NO. In quale intervallo si menti; è nell'intervallo inferiore, (q s) o nell'intervallo superiore, (t v x)? - Si trova nell'intervallo inferiore.

Quindi, l'intervallo inferiore (Q s) deve quindi essere diviso in due. Quando questo viene fatto, l'indice medio per questo intervallo corrisponde a S (2/2 = 1, poiché Q è al nuovo indice 0). L'indice effettivo per S è 6 (d è all'indice originale 0). L'indice del valore riscontrato dovrebbe essere restituito.

Chiave non trovata

Il valore ricercato si chiama chiave. L'elenco ordinato ha effettivamente due indicizzazione come mostrato di seguito:

D	H	N	O	P	Q	S	T	V	X
0	1	2	3	4	5	6	7	8	9
-1	-2	-3	-4	-5	-6	-7	-8	-9	-10

La prima riga di questa tabella ha l'elenco ordinato. La seconda riga ha l'indicizzazione normale. La terza riga ha una sorta di indicizzazione negativa in cui il primo elemento è all'indice -1, il secondo è all'indice -2, il terzo a indice -3 e così via.

Se si trova la chiave, l'algoritmo Java restituirà l'indice normale, a partire da 0. Se la chiave non viene trovata, l'algoritmo Java restituirà l'indice negativo per la posizione che la chiave avrebbe occupato (supponendo che l'array si estendesse a destra di un elemento).

Pacchetto Java e classe per la ricerca binaria

Lo schema di ricerca binaria Java opera su un array già ordinato. Le array di classe Java, che si trova nel Java.util.* pacchetto, ha metodi binarysearch () per la ricerca binaria di un array già ordinato. Ognuno di questi metodi restituisce un numero intero che è un indice normale se si trova la chiave o un indice negativo, come spiegato sopra, se la chiave non viene trovata. Due di questi metodi sono per i caratteri.

Costruire l'array per la ricerca

Il secondo elenco sopra verrà utilizzato per illustrare la codifica di ricerca binaria in Java. La seguente istruzione può essere utilizzata per costruire l'array ordinato:

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;

Lo schema di ricerca binaria Java opera in un elenco già ordinato.

Metodi di ricerca binaria della classe Arrays

La matrice di carattere sopra verrà utilizzata in questa sezione per illustrazione. I metodi di ricerca binaria sono nella classe Arrays del Java.util.* pacchetto. Questo pacchetto deve essere importato per utilizzare la classe Arrays.

Tutti i metodi della classe Array sono metodi statici. Ciò significa che un oggetto non deve essere istanziato per nessuno dei suoi metodi da utilizzare. Due di questi metodi sono metodi di ricerca binaria per i carboni. La sintassi di uno dei metodi di ricerca binaria, per i caratteri è:

Public Static Int BinarySearch (Char [] A, Char Key)

Il seguente programma cerca S che si trova:

Importa Java.util.*;
Classe pubblica TheClass
public static void main (string [] args)
char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret = array.binarysearch (arr, 's');
Sistema.fuori.println (ret);

L'output è 6. Le seguenti segmenti di codice richiedono b, u e z che non sono trovati.

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret1 = array.binarysearch (arr, 'b');
int ret2 = array.binarysearch (arr, 'u');
int ret3 = array.binarysearch (arr, 'z');
Sistema.fuori.stampa (ret1); Sistema.fuori.print ("); sistema.fuori.stampa (ret2);
Sistema.fuori.print ("); sistema.fuori.stampa (ret3); Sistema.fuori.stampa(");
Sistema.fuori.println ();

L'output è,

-1 -9 -11

Ricerca di un intervallo

La sintassi per cercare una gamma di caratteri è:

Public Static int binarySearch (char [] a, int fromindex, int toindex, char key)

dall'indice è l'indice normale in cui inizia l'intervallo. ToIndex è l'indice normale subito dopo l'ultimo elemento dell'intervallo. Il seguente segmento di codice cerca l'array ordinato a partire dall'indice 3 a subito dopo l'indice 7, che è indice 8. L'elemento per l'indice 8 non è incluso nell'intervallo.

char [] arr = new char [] 'd', 'h', 'n', 'o', 'p', 'q', 's', 't', 'v', 'x' ;
int ret = array.binarysearch (arr, 3, 8, 's');
Sistema.fuori.println (ret);

La chiave è S e l'output è 6.

Conclusione

Le sintassi degli array per la ricerca di un array di tipi primitivi sono:

• public static int binarySearch (byte [] a, byte key)
• public static int binarySearch (byte [] a, int fromindex, int toindex, byte key)
• Public Static Int BinarySearch (Char [] A, Char Key)
• Public Static int binarySearch (char [] a, int fromindex, int toindex, char key)
• public static int binarySearch (Double [] A, Double Key)
• public static int binarysearch (doppio [] a, int daindex, int toindex, doppia chiave)
• public static int binarysearch (float [] a, float key)
• public static int binarysearch (float [] a, int daindex, int toindex, float key)
• public static int binarysearch (int [] a, int key)
• public static int binarySearch (int [] a, int fromindex, int toindex, int key)