Подобно бинарному поиску, jump поиск позволяет находить элемент в отсортированном массиве. Основная идея заключается в проверке меньшего количества элементов (чем при линейном поиске), прыгая фиксированными шагами, то есть пропуская некоторые блоки элементов.

Описание алгоритма

К примеру, пусть имеется массив $$arr[]$$ размера $$n$$ отсортированный по возрастанию и блоки размером $$m$$ каждый. Мы просматриваем элементы массива с индексами $$a[0], a[m], a[2m], ..., a[km]$$ в поисках такого $$k$$, что выполняется неравенство $$arr[km] < x < arr[(k+1)m]$$. После нахождения нужного индекса, мы осуществляем линейный поиск в данном блоке начиная с индекса $$km$$, чтобы найти нужный элемент.

Визуализация работы алгоритма

Пусть у нас имеется массивследующий массив (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610) длиной 16. Найдем с помощью Jump search элемент со значением 55. Размер блока для прыжка возьмем равным 4.
Шаг 1: Прыжок от индекса 0 до индекса 4;
Шаг 2: Прыжок от индекса 4 до индекса 8;
Шаг 3: Прыжок от индекса 8 до индекса 16;
Шаг 4: Поскольку элемент с индексом 16 больше чем 55, прыгаем обратно на элемент с индексом 9.
Шаг 5: Проиводим линейны поиск с индекса 9, чтобы найти искомый элемент 55.

Размер оптимального блока

В худшем случае, нам потребуется осуществить $$\dfrac{n}{m}$$ прыжков и в случае если последний проверяемый элемент окажется больше искомого элемента, мы сделаем $$m-1$$ сравнение. Поэтому общее количество сравнений в худшем случае равно $$\dfrac{n}{m} + m-1$$. Функция $$F(n, m) = \dfrac{n}{m} + m-1$$ принимает свое наименьшее значение при $$m=\sqrt{n}$$. Таким образом наилучший размер прыжка равен $$m = \sqrt{n}$$, тогда общее количество сравнений будет равно $$F(n) = 2\sqrt{n} - 1 = \mathcal{O}(\sqrt{n})$$.

Реализация алгоритма

public static int jumpSearch(int[] arr, int x)
    {
        int n = arr.length;

        // Finding block size to be jumped
        int step = (int)Math.floor(Math.sqrt(n));

        // Finding the block where element is
        // present (if it is present)
        int prev = 0;
        while (arr[Math.min(step, n)-1] < x)
        {
            prev = step;
            step += (int)Math.floor(Math.sqrt(n));
            if (prev >= n)
                return -1;
        }

        // Doing a linear search for x in block
        // beginning with prev.
        while (arr[prev] < x)
        {
            prev++;

            // If we reached next block or end of
            // array, element is not present.
            if (prev == Math.min(step, n))
                return -1;
        }

        // If element is found
        if (arr[prev] == x)
            return prev;

        return -1;
    }

Оптимизации

При больших размерах массива, размер одного блока $$m = \sqrt{n}$$ может оказать достаточно большим. Для улучшения эффективности мы можем вместо линейного поиска, рекурсивно применить jump search на блоке в котором содержится искомый элемент. В таком случае сложность алгоритма будет равна

$$ \sqrt{n} + \sqrt{\sqrt{n}} +\sqrt{\sqrt{\sqrt{n}}} + \ldots +1

Такая оптимизация улучшает скорость работы алгоритма, но в худшем случае его сложностьпо прежнему равна $$\mathcal{O}(\sqrt{n})$$Так же поиск можно начинать не с нулевого элемента массива, а сразу с $$k = \sqrt{n}$$.

Реализация оптимизации.

 public static int jumpSearch(int[] arr, int val) {
        int low = 0, high = arr.length - 1;

        while (high - low > 1) {
            Pair p = jumpSearchUtil(arr, val, low, high);

            if (p == null) {
                return -1;
            }

            low = p.left;
            high = p.right;
        }

        return arr[low] == val ? low : arr[high] == val ? high : -1;
    }

    private static Pair jumpSearchUtil(int[] arr, int val, int low, int high) {
        int left = low;
        int step = (int) Math.sqrt(high - low);
        int right = 0;

        while (left < high && arr[left] <= val) {
            right = Math.min(left + step, high);

            if (arr[left] <= val && arr[right] >= val) {
                return new Pair(left, right);
            }

            left = right;
        }

        return null;
    }

}

class Pair {
    int left, right;

    public Pair(int left, int right) {
        this.left = left;
        this.right = right;
    }
}

Сложность алгоритма

Поскольку наилучший размер прыжка равен $$m = \sqrt{n}$$, то общее количество сравнений будет равно $$F(n) = 2\sqrt{n} - 1 = \mathcal{O}(\sqrt{n})$$. Такой алгоритм работает быстрее линейного поиска, но медленнее бинарного поиска.

В случае оптимизированной версии алгоритма, сложность по прежнему равна $$\mathcal{O}(\sqrt{n})$$. Однако теперь его сложность приближается к логарифмическому значению. Проблема состоит в том, что реализация этого поиска с опимизацией считается более сложной, чем двоичный поиск, где сложность также равна $$\mathcal{O} (\log n)$$.

Таблица сравнения сложностей:

	$$10$$	$$10^6$$
$$n$$	10
$$\sqrt{n}$$	4	1000
$$\log n$$	3

Характеристики алгоритма

Класс алгоритма	Алгоритм поиска
Структура данных	отсортированный массив
Худший случай	$$\mathcal{O}(\sqrt{n})$$
Лучший случай	$$\mathcal{O}(\sqrt{n})$$
Средний случай	$$\mathcal{O}(\sqrt{n})$$
Затраты на память	$$\mathcal{O}(1)$$

Приложения

Как и любой алгоритм, Jump Search очень удобен для определенного вида задач. Несмотря на то, что бинарный поиск имеет более простую реализацию, и его сложность $$\mathcal{O}(\log n)$$ лучше чем $$\mathcal{O}(\sqrt{n})$$, в случае очень большого массива прямой переход к середине может быть плохой идеей. Далее мы будем вынуждены много раз отматывать назад, если искомый элемент находится в начале массива.

Каждый из нас совершал в своей жизни примитивный Jump Search поиск, даже не подозревая об этом. Вы помните кассетные магнитофоны? Мы использовали клавишу «перемотка вперед» и периодически проверяли, была ли лента в нашей любимой песне. Как только мы остановились в середине песни, мы использовали кнопку «назад», чтобы найти точное начало песни.

Этот пример, показывает нам когда jump search может быть эффективнее двоичного поиска. Преимущество jump search заключается в том, что вам нужно отскакивать назад только один раз (в случае базовой реализации).

Jump search очень полезен, когда отскакивание назад происходит значительно медленнее, чем вперед!

Особенности

Works only sorted arrays.
The optimal size of a block to be jumped is O(√ n). This makes the time complexity of Jump Search O(√ n).
The time complexity of Jump Search is between Linear Search ( ( O(n) ) and Binary Search ( O (Log n) ).
Binary Search is better than Jump Search, but Jump search has an advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps, consider a situation where the element to be search is the smallest element or smaller than the smallest). So in a systems where jumping back is costly, we use Jump Search.