като Двоично търсене 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).
- Времевата сложност на Jump Search е между линейно търсене ((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 и помогнете на други маниаци. Моля, пишете коментари, ако намерите нещо неправилно или искате да споделите повече информация относно темата, обсъдена по-горе.