Java Academy · leksjon

Arrays.binarySearch

Søk i sorterte arrayer

Leksjon 2 av 413 trinn

Arrays.binarySearch er en gratis leksjon i Java Academy på CoddyKit. Dette er leksjon 2 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Java Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Java Academy inneholder totalt 4 leksjoner.

Søke i sorterte arrayer

Arrays.binarySearch finner et element i en sortert array på O(log n)-tid. Den halverer søkeområdet gjentatte ganger, noe som er langt raskere enn å gå gjennom hvert element.

Forutsetningen om sortering

Arrayen må allerede være sortert i stigende rekkefølge. Hvis den ikke er det, er resultatet udefinert. Bruk alltid Arrays.sort først hvis du er usikker.

Et grunnleggende søk

Når verdien blir funnet, returnerer binarySearch indeksen til den.

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);
    }
}

Når verdien mangler

Hvis verdien ikke finnes, er returverdien negativ: Den er lik -(insertionPoint) - 1. Innsettingspunktet er stedet verdien skulle vært satt inn på for å beholde arrayen sortert.

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);
    }
}

Finne innsettingspunktet

For å gjøre et negativt resultat om til innsettingsindeksen beregner du -(result) - 1. Dette forteller deg hvor den manglende verdien skal settes inn.

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);
        }
    }
}

Søke i objektarrayer

binarySearch fungerer også på objektarrayer ved hjelp av naturlig ordning. Arrayen må være sortert på samme måte som søket sammenligner.

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);
    }
}

Søke med en Comparator

Hvis arrayen ble sortert med en tilpasset Comparator, må du sende inn den samme Comparator-en til binarySearch. Ellers er resultatene meningsløse.

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);
    }
}

Søke i et intervall

Du kan begrense søket til en del av arrayen med binarySearch(array, fromIndex, toIndex, key). Grensene for intervallet følger samme regel om inklusjon og eksklusjon som sortering.

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);
    }
}

Duplikater gir ikke et spesifisert resultat

Hvis arrayen inneholder duplikate verdier, er det ingen garanti for hvilken samsvarende indeks som returneres. Binærsøk egner seg best for arrayer med unike nøkler.

Hvorfor ikke bare bruke en løkke?

Et lineært søk er O(n) og fungerer på usorterte data. Binærsøk er O(log n), men krever sorterte data. Ved gjentatte oppslag i store datasett lønner det seg betydelig å sortere én gang og deretter bruke binærsøk mange ganger.

Sette alt sammen

Sorter, søk, og tolk resultatet på en trygg måte.

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));
        }
    }
}

Rask kontroll

Test forståelsen din av binarySearch.

Besvar den i den interaktive leksjonen

Oppsummering

Du har lært rask søking med Arrays.binarySearch.

Arrayen må sorteres først.
Et ikke-negativt resultat er indeksen der verdien ble funnet.
Et negativt resultat koder innsettingspunktet som -(result) - 1.
Bruk samme Comparator ved sortering og søking.

Gratis å komme i gang

Lær deg Java med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 104
Leksjoner: 374

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Arrays.binarySearch» gratis?

Ja – hele teksten i «Arrays.binarySearch» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Java Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Java Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Arrays.binarySearch»?

Søk i sorterte arrayer Du øver på Java Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Java Academy?

Ingen tidligere erfaring er nødvendig. Java Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 2 av 4.

Hvor lang tid tar leksjonen «Arrays.binarySearch»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Java Academy-leksjonen?

Ja. Alle Java Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til Java Academy