Java Academy · Lezione

Arrays.binarySearch

Cerchi in array ordinati

Arrays.binarySearch è una lezione Java Academy gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Java Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Java Academy include 4 lezioni in totale.

Cercare in array ordinati

Arrays.binarySearch trova un elemento in un array ordinato in un tempo O(log n). Riduce ripetutamente della metà l'intervallo di ricerca, risultando molto più veloce della scansione di ogni elemento.

Il prerequisito dell'ordinamento

L'array deve essere già ordinato in ordine crescente. In caso contrario, il risultato non è definito. Se non è sicuro, utilizzi sempre prima Arrays.sort.

Una ricerca di base

Quando il valore viene trovato, binarySearch restituisce il suo indice.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 8, 10};
        int index = Arrays.binarySearch(nums, 8);
        System.out.println("Found at index " + index);
    }
}

Quando manca il valore

Se il valore non è presente, il valore restituito è negativo: è uguale a -(insertionPoint) - 1. Il punto di inserimento indica la posizione in cui andrebbe collocato il valore per mantenere ordinato l'array.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 8, 10};
        int result = Arrays.binarySearch(nums, 5);
        System.out.println("Raw result: " + result);
    }
}

Recuperare il punto di inserimento

Per trasformare un risultato negativo nell'indice di inserimento, calcoli -(result) - 1. Questo indica dove inserire il valore mancante.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 8, 10};
        int result = Arrays.binarySearch(nums, 5);
        if (result < 0) {
            int insertionPoint = -(result) - 1;
            System.out.println("Would insert at index " + insertionPoint);
        }
    }
}

Cercare in array di oggetti

binarySearch funziona anche sugli array di oggetti utilizzando l'ordinamento naturale. L'array deve essere ordinato nello stesso modo in cui la ricerca esegue i confronti.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String[] names = {"Alice", "Bob", "Charlie", "Dave"};
        int index = Arrays.binarySearch(names, "Charlie");
        System.out.println("Charlie at index " + index);
    }
}

Cercare con un Comparator

Se l'array è stato ordinato con un Comparator personalizzato, deve passare lo stesso Comparator a binarySearch; in caso contrario, i risultati non hanno significato.

import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) {
        String[] names = {"Dave", "Charlie", "Bob", "Alice"};
        Comparator<String> desc = Comparator.reverseOrder();
        Arrays.sort(names, desc);
        int index = Arrays.binarySearch(names, "Charlie", desc);
        System.out.println("Index: " + index);
    }
}

Cercare in un intervallo

Può limitare la ricerca a una parte dell'array con binarySearch(array, fromIndex, toIndex, key). I limiti dell'intervallo seguono la stessa regola di inclusione ed esclusione di sort.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 8, 10, 12};
        int index = Arrays.binarySearch(nums, 1, 5, 8);
        System.out.println("Index: " + index);
    }
}

I duplicati non sono specificati

Se l'array contiene valori duplicati, non vi è alcuna garanzia su quale indice corrispondente venga restituito. La ricerca binaria è più adatta agli array con chiavi univoche.

Perché non usare semplicemente un ciclo?

Una scansione lineare è O(n) e funziona su dati non ordinati. La ricerca binaria è O(log n), ma richiede dati ordinati. Per ricerche ripetute su grandi insiemi di dati, ordinare una volta e usare molte volte la ricerca binaria offre un notevole vantaggio.

Mettere tutto insieme

Ordini, poi cerchi e interpreti il risultato in modo sicuro.

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] ids = {40, 10, 30, 20};
        Arrays.sort(ids);
        int r = Arrays.binarySearch(ids, 30);
        if (r >= 0) {
            System.out.println("Found 30 at index " + r);
        } else {
            System.out.println("Not found; insert at " + (-(r) - 1));
        }
    }
}

Verifica rapida

Verifichi la Sua comprensione di binarySearch.

Riepilogo

Ha imparato a eseguire ricerche rapide con Arrays.binarySearch.

L'array deve essere ordinato prima della ricerca.
Un risultato non negativo è l'indice dell'elemento trovato.
Un risultato negativo codifica il punto di inserimento come -(result) - 1.
Utilizzi lo stesso Comparator per l'ordinamento e la ricerca.

Domande Frequenti

La lezione «Arrays.binarySearch» è gratuita?

Sì — il testo completo di «Arrays.binarySearch» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Java Academy, passa a CoddyKit PRO. Il corso Java Academy include 4 lezioni in totale.

Cosa imparerò in «Arrays.binarySearch»?

Cerchi in array ordinati Eserciti Java Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare Java Academy?

Non è richiesta alcuna esperienza precedente. Java Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.

Quanto tempo richiede la lezione «Arrays.binarySearch»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione Java Academy?

Sì. Ogni lezione Java Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a Java Academy