Поиск элемента в массиве в Java

Достаточно частая задача — поиск элемента в массиве. Допустим, у нас есть массив:

int[] array = {1, 5, 8, 10, 16, 20, ..., 100};

и нам нужно найти позицию (индекс) элемента 10 или просто выяснить, есть ли такой элемент в массиве.

В зависимости от размера данных и требований к скорости работы применяют разные алгоритмы поиска. Основные из них:

• Линейный поиск — O(n)
• Двоичный поиск — O(log n)
• Поиск прыжками — O(sqrt n)
• Интерполяционный поиск — O(log log n)
• Экспоненциальный поиск — O(log n)

Разберём наиболее популярные из них с примерами на Java.

1. Линейный поиск (Linear Search)

Простой, но не самый быстрый метод. Мы просто перебираем элементы массива по порядку и сравниваем каждый с целевым значением. Как только нашли совпадение — возвращаем индекс, если дошли до конца — возвращаем -1.

public static int linearSearch(int[] array, int elementToSearch) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == elementToSearch) {
            return i;
        }
    }
    return -1;
}

Время выполнения: O(n)
Подходит: для неотсортированных массивов и небольших объёмов данных. Это единственный из рассмотренных способов, который не требует предварительной сортировки.

2. Двоичный поиск (Binary Search) — итеративный подход

Более эффективный алгоритм. Работает только с отсортированными массивами. Суть — итеративно делим массив пополам: берём «средний элемент» с индексом middleIndex и сравниваем с искомым. Если они равны — поиск завершён. Если искомый элемент меньше среднего, отбрасываем правую часть массива, иначе — левую. Повторяем, пока элемент не найден или пока отрезок не станет пустым. Если элемент не нашёлся, возвращаем -1.

public static int binarySearch(int[] array, int elementToSearch) {
        int firstIndex = 0;
        int lastIndex = array.length - 1;

        // условие прекращения (элемент не представлен)
        while (firstIndex <= lastIndex) {
            int middleIndex = (firstIndex + lastIndex) / 2;
            // если средний элемент - целевой элемент, вернуть его индекс
            if (array[middleIndex] == elementToSearch) {
                return middleIndex;
            }

            // если средний элемент меньше
            // направляем наш индекс в middle+1, убирая первую часть из рассмотрения
            else if (array[middleIndex] < elementToSearch) {
                firstIndex = middleIndex + 1;
            }
            // если средний элемент больше
            // направляем наш индекс в middle-1, убирая вторую часть из рассмотрения
            else if (array[middleIndex] > elementToSearch) {
                lastIndex = middleIndex - 1;
            }
        }
        return -1;
    }

Время выполнения: O(log n)
Подходит: для отсортированных массивов.

3. Двоичный поиск — рекурсивный подход

Та же идея, но реализованная через рекурсию: на каждом шаге метод вызывает сам себя для суженного диапазона.

public static int recursiveBinarySearch(int[] array, int firstElement, int lastElement, int elementToSearch) {
        // условие прекращения
        if (lastElement >= firstElement) {
            int middle = (lastElement + firstElement) / 2;

            // если средний элемент - целевой элемент, вернуть его индекс
            if (array[middle] == elementToSearch) {
                return middle;
            }

            // если средний элемент больше целевого
            // вызываем метод рекурсивно по суженным данным
            if (array[middle] > elementToSearch) {
                return recursiveBinarySearch(array, firstElement, middle - 1, elementToSearch);
            }

            // также, вызываем метод рекурсивно по суженным данным
            return recursiveBinarySearch(array, middle + 1, lastElement, elementToSearch);
        }
        return -1;
    }

Время выполнения: O(log n)
Плюс: код короче, логика читается проще.
Минус: JVM не выполняет оптимизацию хвостовой рекурсии (tail call), поэтому теоретически на очень глубоком дереве вызовов возможен StackOverflowError. На практике для двоичного поиска глубина всего O(log n), так что это скорее нюанс, чем реальный риск.

4. Поиск прыжками (Jump Search)

Подходит для отсортированных массивов. Алгоритм перескакивает вперёд через фиксированное количество элементов (обычно шаг равен √n), пока не «перепрыгнет» искомое значение, а затем делает линейный поиск внутри найденного блока.

public static int jumpSearch(int[] array, int elementToSearch) {
        int arrayLength = array.length;
        int jumpStep = (int) Math.sqrt(array.length);
        int previousStep = 0;

        while (array[Math.min(jumpStep, arrayLength) - 1] < elementToSearch) {
            previousStep = jumpStep;
            jumpStep += (int) (Math.sqrt(arrayLength));
            if (previousStep >= arrayLength) {
                return -1;
            }
        }
        while (array[previousStep] < elementToSearch) {
            previousStep++;
            if (previousStep == Math.min(jumpStep, arrayLength)) {
                return -1;
            }
        }

        if (array[previousStep] == elementToSearch) {
            return previousStep;
        }
        return -1;
    }

Время выполнения: O(sqrt n)
Подходит: для больших отсортированных массивов, когда «шаг назад» дороже «шага вперёд» (например, при последовательном чтении с носителя).

Готовые средства Java: без ручной реализации

В реальном коде свой алгоритм писать чаще всего не нужно — в стандартной библиотеке уже есть проверенные решения:

• Arrays.binarySearch(array, key) — двоичный поиск по отсортированному массиву. Возвращает индекс элемента или отрицательное число, если его нет.
• Для коллекций — list.indexOf(element) (линейный поиск) и Collections.binarySearch(list, key).
• Через Stream API удобно проверять наличие: IntStream.of(array).anyMatch(x -> x == key).

int[] array = {1, 5, 8, 10, 16, 20};
int index = Arrays.binarySearch(array, 10); // 3

Сравнение алгоритмов

Заключение

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

Итог: выбор алгоритма зависит от структуры данных, размера массива и требований к скорости. В прикладном коде в большинстве случаев достаточно стандартного Arrays.binarySearch.