Java Academy · Урок

Arrays.binarySearch

Ищите в отсортированных массивах

«Arrays.binarySearch» — бесплатный урок Java Academy на CoddyKit. Это урок 2 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Java Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Java Academy содержит 4 уроков всего.

Поиск в отсортированных массивах

Arrays.binarySearch находит элемент в отсортированном массиве за время O(log n). Метод неоднократно делит диапазон поиска пополам, поэтому работает намного быстрее, чем просмотр каждого элемента.

Предварительное условие сортировки

Массив уже должен быть отсортирован по возрастанию. Если это не так, результат не определён. Если Вы не уверены, сначала всегда вызывайте Arrays.sort.

Простой поиск

Если значение найдено, binarySearch возвращает его индекс.

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

Если значение отсутствует

Если значения нет в массиве, возвращаемое значение является отрицательным: оно равно -(insertionPoint) - 1. Точка вставки — это место, куда можно было бы поместить значение, сохранив сортировку массива.

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

Восстановление точки вставки

Чтобы преобразовать отрицательный результат в индекс вставки, вычислите -(result) - 1. Так Вы узнаете, куда вставить отсутствующее значение.

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

Поиск в массивах объектов

binarySearch также работает с массивами объектов, используя естественный порядок. Массив должен быть отсортирован тем же способом, которым выполняется сравнение при поиске.

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

Поиск с компаратором

Если массив был отсортирован с помощью собственного Comparator, необходимо передать тот же Comparator в binarySearch, иначе результаты не имеют смысла.

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

Поиск в диапазоне

Вы можете ограничить поиск частью массива с помощью binarySearch(array, fromIndex, toIndex, key). Границы диапазона подчиняются тому же правилу включения и исключения, что и при сортировке.

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

Поведение при дубликатах не определено

Если массив содержит повторяющиеся значения, не гарантируется, какой из совпадающих индексов будет возвращён. Двоичный поиск лучше всего использовать для массивов с уникальными ключами.

Почему бы просто не использовать цикл

Линейный поиск выполняется за O(n) и работает с неотсортированными данными. Двоичный поиск выполняется за O(log n), но требует отсортированных данных. При многократном поиске в больших наборах данных сортировка один раз и последующее многократное выполнение двоичного поиска дают значительный выигрыш.

Собираем всё вместе

Сначала отсортируйте массив, затем выполните поиск и безопасно интерпретируйте результат.

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

Быстрая проверка

Проверьте своё понимание binarySearch.

Итоги

Вы изучили быстрый поиск с помощью Arrays.binarySearch.

Сначала массив необходимо отсортировать.
Неотрицательный результат — это индекс найденного элемента.
Отрицательный результат кодирует точку вставки как -(result) - 1.
Используйте один и тот же Comparator для сортировки и поиска.

Часто задаваемые вопросы

Урок «Arrays.binarySearch» бесплатный?

Да — полный текст урока «Arrays.binarySearch» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Java Academy, подпишись на CoddyKit PRO. Курс Java Academy содержит 4 уроков всего.

Чему я научусь в уроке «Arrays.binarySearch»?

Ищите в отсортированных массивах Ты практикуешь Java Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Java Academy?

Предыдущий опыт не требуется. Java Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 2 из 4.

Сколько времени занимает урок «Arrays.binarySearch»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Java Academy?

Да. Каждый урок Java Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к Java Academy