Java Academy · Lekcja

Arrays.binarySearch

Przeszukuj posortowane tablice

Arrays.binarySearch to bezpłatna lekcja Java Academy na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Java Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Java Academy zawiera 4 lekcji w sumie.

Wyszukiwanie w posortowanych tablicach

Arrays.binarySearch wyszukuje element w posortowanej tablicy w czasie O(log n). Wielokrotnie dzieli zakres wyszukiwania na pół, dzięki czemu działa znacznie szybciej niż sprawdzanie każdego elementu po kolei.

Warunek wstępny: posortowana tablica

Tablica musi być już posortowana rosnąco. Jeśli nie jest, wynik jest nieokreślony. Jeśli nie masz pewności, zawsze najpierw wywołaj Arrays.sort.

Podstawowe wyszukiwanie

Gdy wartość zostanie znaleziona, binarySearch zwraca jej indeks.

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

Gdy brakuje wartości

Jeśli wartości nie ma w tablicy, zwracana wartość jest ujemna: odpowiada wyrażeniu -(insertionPoint) - 1. Punkt wstawienia wskazuje miejsce, w którym należałoby umieścić wartość, aby zachować uporządkowanie tablicy.

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

Odczytywanie punktu wstawienia

Aby przekształcić ujemny wynik w indeks wstawienia, oblicz -(result) - 1. Dzięki temu dowiesz się, gdzie wstawić brakującą wartość.

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

Wyszukiwanie w tablicach obiektów

binarySearch działa także na tablicach obiektów, używając naturalnego porządku. Tablica musi być posortowana w taki sam sposób, w jaki metoda wyszukiwania porównuje elementy.

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

Wyszukiwanie za pomocą Comparator

Jeśli tablica została posortowana za pomocą niestandardowego obiektu Comparator, musisz przekazać ten sam obiekt Comparator do binarySearch. W przeciwnym razie wyniki nie będą miały sensu.

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

Wyszukiwanie w zakresie

Możesz ograniczyć wyszukiwanie do części tablicy za pomocą binarySearch(array, fromIndex, toIndex, key). Granice zakresu podlegają tej samej zasadzie: początek jest włączony, a koniec wyłączony, co w przypadku sortowania.

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

Brak określonego wyniku dla duplikatów

Jeśli tablica zawiera zduplikowane wartości, nie ma gwarancji, który z pasujących indeksów zostanie zwrócony. Wyszukiwanie binarne najlepiej stosować w przypadku tablic z unikatowymi kluczami.

Dlaczego nie użyć zwykłej pętli?

Wyszukiwanie liniowe działa w czasie O(n) i sprawdza się dla nieposortowanych danych. Wyszukiwanie binarne działa w czasie O(log n), ale wymaga posortowanych danych. W przypadku wielokrotnych wyszukiwań w dużych zbiorach danych jednorazowe sortowanie, a następnie wielokrotne wyszukiwanie binarne daje dużą korzyść.

Połączenie wszystkiego

Posortuj tablicę, następnie wyszukaj wartość i bezpiecznie zinterpretuj wynik.

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

Szybki test

Sprawdź swoje rozumienie działania binarySearch.

Podsumowanie

Nauczyłeś się szybkiego wyszukiwania za pomocą Arrays.binarySearch.

Najpierw tablica musi zostać posortowana.
Nieujemny wynik to indeks znalezionego elementu.
Ujemny wynik koduje punkt wstawienia jako -(result) - 1.
Do sortowania i wyszukiwania używaj tego samego obiektu Comparator.

Często zadawane pytania

Czy lekcja „Arrays.binarySearch” jest bezpłatna?

Tak — pełny tekst „Arrays.binarySearch” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Java Academy, przejdź na CoddyKit PRO. Kurs Java Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Arrays.binarySearch”?

Przeszukuj posortowane tablice Ćwiczysz Java Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Java Academy?

Nie wymagamy żadnego doświadczenia. Java Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.

Ile czasu zajmuje lekcja „Arrays.binarySearch”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Java Academy?

Tak. Każda lekcja Java Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do Java Academy