Рубрики

Прыжок Поиск

Как и бинарный поиск , Jump Search — это алгоритм поиска отсортированных массивов. Основная идея состоит в том, чтобы проверять меньшее количество элементов (чем при линейном поиске ), перепрыгивая вперед с фиксированными шагами или пропуская некоторые элементы вместо поиска всех элементов.

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

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

Каков оптимальный размер блока для пропуска?
В худшем случае нам нужно выполнить n / m переходов, и если последнее проверенное значение больше, чем искомый элемент, мы выполняем сравнение m-1 для линейного поиска. Поэтому общее количество сравнений в худшем случае будет ((н / м) + м-1). Значение функции ((n / m) + m-1) будет минимальным, когда m = √n. Следовательно, наилучший размер шага — m = √n.

C ++

// C ++ программа для реализации Jump Search

  
#include <bits/stdc++.h>

using namespace std;

  

int jumpSearch(int arr[], int x, int n)

{

    // Находим размер блока для перехода

    int step = sqrt(n);

  

    // Находим блок, где находится элемент

    // присутствует (если есть)

    int prev = 0;

    while (arr[min(step, n)-1] < x)

    {

        prev = step;

        step += sqrt(n);

        if (prev >= n)

            return -1;

    }

  

    // Выполнение линейного поиска x в блоке

    // начиная с пред.

    while (arr[prev] < x)

    {

        prev++;

  

        // Если мы достигли следующего блока или конца

        // массив, элемент отсутствует.

        if (prev == min(step, n))

            return -1;

    }

    // Если элемент найден

    if (arr[prev] == x)

        return prev;

  

    return -1;

}

  
// Программа драйвера для тестирования функции

int main()

{

    int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,

                34, 55, 89, 144, 233, 377, 610 };

    int x = 55;

    int n = sizeof(arr) / sizeof(arr[0]);

      

    // Находим индекс 'x' с помощью Jump Search

    int index = jumpSearch(arr, x, n);

  

    // Распечатать индекс, где находится 'x'

    cout << "\nNumber " << x << " is at index " << index;

    return 0;

}

  
// Предоставлено nuclode

Джава

// Java-программа для реализации Jump Search.

public class JumpSearch

{

    public static int jumpSearch(int[] arr, int x)

    {

        int n = arr.length;

  

        // Находим размер блока для перехода

        int step = (int)Math.floor(Math.sqrt(n));

  

        // Находим блок, где находится элемент

        // присутствует (если есть)

        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;

        }

  

        // Выполнение линейного поиска x в блоке

        // начиная с пред.

        while (arr[prev] < x)

        {

            prev++;

  

            // Если мы достигли следующего блока или конца

            // массив, элемент отсутствует.

            if (prev == Math.min(step, n))

                return -1;

        }

  

        // Если элемент найден

        if (arr[prev] == x)

            return prev;

  

        return -1;

    }

  

    // Программа драйвера для тестирования функции

    public static void main(String [ ] args)

    {

        int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,

                    34, 55, 89, 144, 233, 377, 610};

        int x = 55;

  

        // Находим индекс 'x' с помощью Jump Search

        int index = jumpSearch(arr, x);

  

        // Распечатать индекс, где находится 'x'

        System.out.println("\nNumber " + x +

                            " is at index " + index);

    }

}

python3

# Python3 код для реализации Jump Search

import math

  

def jumpSearch( arr , x , n ):

      

    # Нахождение размера блока для прыжка

    step = math.sqrt(n)

      

    # Нахождение блока, где находится элемент

    # присутствует (если есть)

    prev = 0

    while arr[int(min(step, n)-1)] < x:

        prev = step

        step += math.sqrt(n)

        if prev >= n:

            return -1

      

    # Выполняя линейный поиск х в

    # блок, начинающийся с пред.

    while arr[int(prev)] < x:

        prev += 1

          

        # Если мы достигли следующего блока или конца

        # массива, элемента нет.

        if prev == min(step, n):

            return -1

      

    # Если элемент найден

    if arr[int(prev)] == x:

        return prev

      

    return -1

  
# Код драйвера для проверки функции

arr = [ 0, 1, 1, 2, 3, 5, 8, 13, 21,

    34, 55, 89, 144, 233, 377, 610 ]

x = 55

n = len(arr)

  
# Найти индекс 'x' с помощью Jump Search

index = jumpSearch(arr, x, n)

  
# Распечатать индекс, где находится «х»

print("Number" , x, "is at index" ,"%.0f"%index)

  
# Этот код предоставлен "Sharad_Bhardwaj".

C #

// C # программа для реализации Jump Search.

using System;

public class JumpSearch

{

    public static int jumpSearch(int[] arr, int x)

    {

        int n = arr.Length;

  

        // Находим размер блока для перехода

        int step = (int)Math.Floor(Math.Sqrt(n));

  

        // Находим блок, где находится элемент

        // присутствует (если есть)

        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;

        }

  

        // Выполнение линейного поиска x в блоке

        // начиная с пред.

        while (arr[prev] < x)

        {

            prev++;

  

            // Если мы достигли следующего блока или конца

            // массив, элемент отсутствует.

            if (prev == Math.Min(step, n))

                return -1;

        }

  

        // Если элемент найден

        if (arr[prev] == x)

            return prev;

  

        return -1;

    }

  

    // Программа драйвера для тестирования функции

    public static void Main()

    {

        int[] arr = { 0, 1, 1, 2, 3, 5, 8, 13, 21,

                    34, 55, 89, 144, 233, 377, 610};

        int x = 55;

  

        // Находим индекс 'x' с помощью Jump Search

        int index = jumpSearch(arr, x);

  

        // Распечатать индекс, где находится 'x'

        Console.Write("Number " + x +

                            " is at index " + index);

    }

}

PHP

<?php 
// PHP-программа для реализации Jump Search

  

function jumpSearch($arr, $x, $n)

{

    // Находим размер блока для перехода

    $step = sqrt($n);

  

    // Находим блок, где находится элемент

    // присутствует (если есть)

    $prev = 0;

    while ($arr[min($step, $n)-1] < $x)

    {

        $prev = $step;

        $step += sqrt($n);

        if ($prev >= $n)

            return -1;

    }

  

    // Выполнение линейного поиска x в блоке

    // начиная с пред.

    while ($arr[$prev] < $x)

    {

        $prev++;

  

        // Если мы достигли следующего блока или конца

        // массив, элемент отсутствует.

        if ($prev == min($step, $n))

            return -1;

    }

    // Если элемент найден

    if ($arr[$prev] == $x)

        return $prev;

  

    return -1;

}

  
// Программа драйвера для тестирования функции

$arr = array( 0, 1, 1, 2, 3, 5, 8, 13, 21,

                34, 55, 89, 144, 233, 377, 610 );

$x = 55;

$n = sizeof($arr) / sizeof($arr[0]);

      
// Находим индекс $ x с помощью Jump Search

$index = jumpSearch($arr, $x, $n);

  
// Распечатать индекс, где находится $ x

echo "Number ".$x." is at index " .$index;

return 0;

?>


Выход:

Number 55 is at index 10

Сложность времени: O (√n)
Вспомогательное пространство: O (1)

Важные моменты:

  • Работает только отсортированные массивы.
  • Оптимальный размер блока для прыжка равен (√ n). Это делает временную сложность Jump Search O (√ n).
  • Временная сложность поиска перехода между линейным поиском ((O (n)) и бинарным поиском (O (Log n)).
  • Бинарный поиск лучше, чем поиск с переходом, но преимущество поиска с переходом имеет то преимущество, что мы переходим обратно только один раз (для бинарного поиска может потребоваться до O (Log n) переходов, рассмотрим ситуацию, когда искомый элемент является наименьшим элементом или меньше, чем наименьший). Таким образом, в системе, где бинарный поиск обходится дорого, мы используем Jump Search.

Ссылки:
https://en.wikipedia.org/wiki/Jump_search

Эта статья предоставлена Суровым Агарвалом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогайте другим Geeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Прыжок Поиск

0.00 (0%) 0 votes