Поиск ПрыжкамиJump Search

Выбирается фиксированный размер блока step (оптимальное значение — √n, обоснование ниже). Указатель прыгает по массиву с этим шагом (0, step, 2·step, ...), пока не встретит блок, чей последний элемент ≥ x, или не дойдёт до конца массива. На этом этапе известно: если x есть в массиве, он лежит в диапазоне (предыдущая позиция прыжка, текущая позиция] — потому что все более ранние блоки целиком меньше x (иначе прыжок остановился бы раньше). Второй этап — обычный линейный поиск внутри этого диапазона размера не больше step.A fixed block size step is chosen (the optimal value is √n, justified below). A pointer jumps through the array with this stride (0, step, 2·step, ...) until it hits a block whose last element is ≥ x, or reaches the array's end. At this point it's known: if x is in the array, it lies within (previous jump position, current position] — because every earlier block was entirely less than x (otherwise the jump would have stopped sooner). The second stage is ordinary linear search within that range of size at most step.

int jump_search(const std::vector<int>& a, int x) {
    int n = (int)a.size();
    if (n == 0) return -1;
    int step = std::max(1, (int)std::sqrt(n));

    int prev = 0, curr = step;
    while (curr < n && a[curr - 1] < x) {  // прыгаем, пока блок целиком меньше x// jump while the block is entirely less than x
        prev = curr;
        curr += step;
    }
    int hi = std::min(curr, n);
    for (int i = prev; i < hi; ++i)          // линейный поиск внутри найденного блока// linear search inside the found block
        if (a[i] == x) return i;
    return -1;
}

Столбики сгруппированы в блоки размера step = √n (жёлтая рамка обозначает границы блоков). Оранжевая подсветка — текущий проверяемый последний элемент блока во время прыжков; зелёная — линейный поиск внутри найденного блока.Bars are grouped into blocks of size step = √n (a yellow outline marks block boundaries). Orange highlights the block's last element being checked during the jump phase; green marks linear search inside the found block.

Число прыжков в худшем случае — n/step (нужно пройти весь массив блоками), число сравнений линейного поиска в найденном блоке — до step. Суммарная стоимость f(step) = n/step + step. Чтобы её минимизировать, берём производную по step и приравниваем к нулю: f'(step) = -n/step² + 1 = 0 → step² = n → step = √n. При этом выборе f(√n) = √n + √n = 2√n — то есть общее число операций в худшем случае Θ(√n), что и является доказанной, а не эмпирически подобранной, оптимальной точкой компромисса между "много мелких прыжков" и "один большой линейный поиск".The worst-case number of jumps is n/step (the whole array must be covered in blocks), and linear-search comparisons inside the found block go up to step. The total cost is f(step) = n/step + step. To minimize it, take the derivative with respect to step and set it to zero: f'(step) = -n/step² + 1 = 0 → step² = n → step = √n. With this choice, f(√n) = √n + √n = 2√n — so the total worst-case operation count is Θ(√n), a proven (not empirically tuned) optimal trade-off point between "many small jumps" and "one large linear search."