Java Academy · Lektion

Arrays.binarySearch

Sök i sorterade arrayer

Lektion 2 av 413 steg

Arrays.binarySearch är en gratis lektion i Java Academy på CoddyKit. Detta är lektion 2 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Java Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Java Academy innehåller totalt 4 lektioner.

Söka i sorterade arrayer

Arrays.binarySearch hittar ett element i en sorterad array på O(log n)-tid. Metoden halverar sökintervallet upprepade gånger, vilket är mycket snabbare än att gå igenom varje element.

Kravet på sortering

Arrayen måste redan vara sorterad i stigande ordning. Om den inte är det är resultatet odefinierat. Anropa alltid Arrays.sort först om ni är osäkra.

En grundläggande sökning

När värdet hittas returnerar binarySearch dess index.

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 värdet saknas

Om värdet inte finns är returvärdet negativt: det är lika med -(insertionPoint) - 1. Insättningspunkten är den plats där värdet skulle placeras för att behålla arrayens sortering.

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

Hämta insättningspunkten

Om ni vill omvandla ett negativt resultat till insättningsindexet beräknar ni -(result) - 1. Det visar var det saknade värdet ska infogas.

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öka i objektarrayer

binarySearch fungerar även på objektarrayer med naturlig ordning. Arrayen måste vara sorterad på samma sätt som sökningen jämför elementen.

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öka med en Comparator

Om arrayen sorterades med en anpassad Comparator måste samma Comparator skickas till binarySearch. Annars saknar resultaten betydelse.

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öka i ett intervall

Ni kan begränsa sökningen till en del av arrayen med binarySearch(array, fromIndex, toIndex, key). Intervallgränserna följer samma regel om inkluderande och exkluderande gräns 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);
    }
}

Dubbletter ger inget specificerat resultat

Om arrayen innehåller dubblettvärden finns det ingen garanti för vilket matchande index som returneras. Binär sökning lämpar sig bäst för arrayer med unika nycklar.

Varför inte bara använda en loop

En linjär genomsökning är O(n) och fungerar på osorterade data. Binär sökning är O(log n), men kräver sorterade data. Vid upprepade sökningar i stora datamängder lönar det sig mycket att sortera en gång och sedan använda binär sökning många gånger.

Sätt ihop delarna

Sortera, sök och tolka sedan resultatet på ett säkert sätt.

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

Snabb kontroll

Testa era kunskaper om binarySearch.

Besvara frågan i den interaktiva lektionen

Sammanfattning

Ni har lärt er snabb sökning med Arrays.binarySearch.

Arrayen måste sorteras först.
Ett icke-negativt resultat är det hittade indexet.
Ett negativt resultat kodar insättningspunkten som -(result) - 1.
Använd samma Comparator vid sortering och sökning.

Gratis att börja

Lär dig Java med en AI-lärare – gratis

Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.

Kurser: 104
Lektioner: 374

Börja lära dig gratis Visa hela kursen

Vanliga frågor

Är lektionen ”Arrays.binarySearch” gratis?

Ja – hela texten till ”Arrays.binarySearch” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Java Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Java Academy innehåller totalt 4 lektioner.

Vad lär jag mig i ”Arrays.binarySearch”?

Sök i sorterade arrayer Ni övar på Java Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.

Behöver jag någon erfarenhet för att börja lära mig Java Academy?

Du behöver inga förkunskaper. Utbildningen i Java Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.

Hur lång tid tar lektionen ”Arrays.binarySearch”?

De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.

Kan jag skriva och köra kod i den här Java Academy-lektionen?

Ja. Varje Java Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.

Alla lektioner i den här kursen

← Tillbaka till Java Academy