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

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

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

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

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

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

Рассмотрим подробнее наиболее популярные.

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

Простой, но неэффективный метод. Мы просто перебираем элементы массива и сравниваем каждый с целевым значением.

    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)
Плюс: код короче, логика проще
Минус: возможен StackOverflow на больших массивах без tail recursion

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(√n)
Подходит: при частом поиске в больших отсортированных массивах

Заключение

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

 

Важно: Выбор алгоритма зависит от структуры данных, размера массива и необходимости в производительности.

Курс 'Java для начинающих' на Udemy