Подобається Двійковий пошук Jump Search — це алгоритм пошуку відсортованих масивів. Основна ідея полягає в тому, щоб перевірити менше елементів (ніж лінійний пошук ), переходячи вперед на фіксовані кроки або пропускаючи деякі елементи замість пошуку всіх елементів.
Наприклад, припустимо, що у нас є масив arr[] розміром n і блок (до якого потрібно перейти) розміром m. Потім ми шукаємо в індексах arr[0] arr[m] arr[2m].....arr[km] і так далі. Коли ми знайдемо інтервал (arr[km]< x < arr[(k+1)m]) we perform a linear search operation from the index km to find the element 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.
Продуктивність порівняно з лінійним і бінарним пошуком:
Якщо порівняти його з лінійним і двійковим пошуком, то виходить, що він кращий за лінійний пошук, але не кращий за двійковий пошук.
У порядку зростання продуктивності є:
лінійний пошук < jump search < binary search
Який оптимальний розмір блоку, який потрібно пропустити?
У гіршому випадку ми повинні зробити n/m стрибків, і якщо останнє перевірене значення більше, ніж елемент, який потрібно шукати, ми виконуємо порівняння m-1 більше для лінійного пошуку. Тому загальна кількість порівнянь у найгіршому випадку буде ((n/m) + m-1). Значення функції ((n/m) + m-1) буде мінімальним, коли m = √n. Тому найкращий розмір кроку m = √ п.
Етапи алгоритму
- Jump Search — це алгоритм пошуку певного значення у відсортованому масиві шляхом переходу через певні кроки в масиві.
- Кроки визначаються sqrt довжини масиву.
- Ось покроковий алгоритм пошуку переходу:
- Визначте розмір кроку m, взявши sqrt довжини масиву n.
- Почніть з першого елемента масиву та переходьте на m кроків, поки значення в цій позиції не стане більшим за цільове значення.
Якщо знайдено значення, яке перевищує цільове, виконайте лінійний пошук, починаючи з попереднього кроку, доки ціль не буде знайдено або поки не стане ясно, що ціль відсутня в масиві.
Якщо ціль знайдено, поверніть її індекс. Якщо ні повертає -1, щоб вказати, що ціль не знайдено в масиві.
Приклад 1:
C++// C++ program to implement Jump Search #include
#include
// Java program to implement Jump Search. public class JumpSearch { 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; for (int minStep = Math.min(step n)-1; arr[minStep] < x; minStep = Math.min(step n)-1) { 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; } // Driver program to test function 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; // Find the index of 'x' using Jump Search int index = jumpSearch(arr x); // Print the index where 'x' is located System.out.println('nNumber ' + x + ' is at index ' + index); } }
# Python3 code to implement Jump Search import math def jumpSearch( arr x n ): # Finding block size to be jumped step = math.sqrt(n) # Finding the block where element is # present (if it is present) prev = 0 while arr[int(min(step n)-1)] < x: prev = step step += math.sqrt(n) if prev >= n: return -1 # Doing a linear search for x in # block beginning with prev. while arr[int(prev)] < x: prev += 1 # If we reached next block or end # of array element is not present. if prev == min(step n): return -1 # If element is found if arr[int(prev)] == x: return prev return -1 # Driver code to test function arr = [ 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ] x = 55 n = len(arr) # Find the index of 'x' using Jump Search index = jumpSearch(arr x n) # Print the index where 'x' is located print('Number' x 'is at index' '%.0f'%index) # This code is contributed by 'Sharad_Bhardwaj'.
// C# program to implement Jump Search. using System; public class JumpSearch { public static int jumpSearch(int[] arr int x) { int n = arr.Length; // Finding block size to be jumped int step = (int)Math.Sqrt(n); // Finding the block where the element is // present (if it is present) int prev = 0; for (int minStep = Math.Min(step n)-1; arr[minStep] < x; minStep = Math.Min(step n)-1) { prev = step; step += (int)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; } // Driver program to test function 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; // Find the index of 'x' using Jump Search int index = jumpSearch(arr x); // Print the index where 'x' is located Console.Write('Number ' + x + ' is at index ' + index); } }
<script> // Javascript program to implement Jump Search function jumpSearch(arr x n) { // Finding block size to be jumped let step = Math.sqrt(n); // Finding the block where element is // present (if it is present) let prev = 0; for (int minStep = Math.Min(step n)-1; arr[minStep] < x; minStep = Math.Min(step n)-1) { prev = step; step += 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; } // Driver program to test function let arr = [0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610]; let x = 55; let n = arr.length; // Find the index of 'x' using Jump Search let index = jumpSearch(arr x n); // Print the index where 'x' is located document.write(`Number ${x} is at index ${index}`); // This code is contributed by _saurabh_jaiswal </script>
// PHP program to implement Jump Search function jumpSearch($arr $x $n) { // Finding block size to be jumped $step = sqrt($n); // Finding the block where element is // present (if it is present) $prev = 0; while ($arr[min($step $n)-1] < $x) { $prev = $step; $step += 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 == min($step $n)) return -1; } // If element is found if ($arr[$prev] == $x) return $prev; return -1; } // Driver program to test function $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]); // Find the index of '$x' using Jump Search $index = jumpSearch($arr $x $n); // Print the index where '$x' is located echo 'Number '.$x.' is at index ' .$index; return 0; ?> Вихід:
Number 55 is at index 10
Часова складність: O(?n)
Допоміжний простір: O(1)
Переваги Jump Search:
- Краще, ніж лінійний пошук масивів, де елементи рівномірно розподілені.
- Перехідний пошук має меншу часову складність порівняно з лінійним пошуком для великих масивів.
- Кількість кроків, виконаних під час пошуку переходів, пропорційна квадратному кореню з розміру масиву, що робить його більш ефективним для великих масивів.
- Його легше реалізувати порівняно з іншими алгоритмами пошуку, такими як двійковий або потрійний пошук.
- Перехідний пошук добре працює для масивів, де елементи розташовані в порядку та рівномірно розподілені, оскільки він може переходити до ближчої позиції в масиві з кожною ітерацією.
Важливі моменти:
сортування вибору
- Працює лише з відсортованими масивами.
- Оптимальний розмір блоку, який потрібно перейти, це (? n). Це робить часову складність Jump Search O(? n).
- Часова складність пошуку з переходом знаходиться між лінійним пошуком ((O(n)) і бінарним пошуком (O(Log n)).
- Двійковий пошук кращий, ніж Jump Search, але Jump Search має ту перевагу, що ми повертаємося назад лише один раз (Binary Search може вимагати до O(Log n) переходів, розглядаючи ситуацію, коли елемент, який потрібно шукати, є найменшим елементом або просто більшим за найменший). Тому в системі, де бінарний пошук дорогий, ми використовуємо Jump Search.
Література:
https://en.wikipedia.org/wiki/Jump_search
Якщо вам подобається GeeksforGeeks і ви хочете зробити свій внесок, ви також можете написати статтю за допомогою write.geeksforgeeks.org або надішліть свою статтю на адресу [email protected]. Подивіться, як ваша стаття з’являється на головній сторінці GeeksforGeeks, і допоможіть іншим гікам. Будь ласка, пишіть коментарі, якщо ви знайдете щось невірне або хочете поділитися додатковою інформацією про тему, розглянуту вище.