像二進(jìn)制搜索一樣，跳躍搜索是排序數(shù)組的搜索算法?；舅枷胧峭ㄟ^(guò)固定步驟跳過(guò)或跳過(guò)某些元素代替搜索所有元素來(lái)檢查較少的元素（而不是線性搜索）。

例如，假設(shè)我們有一個(gè)大小為n的數(shù)組arr []和塊（要跳轉(zhuǎn)）的大小m。然后我們搜索索引arr [0]，arr [m]，arr [2m] ... ..arr [km]等等。一旦我們找到間隔（arr [km] <x <arr [（k + 1）m]），我們從索引km執(zhí)行線性搜索操作來(lái)找到元素x。

我們考慮以下數(shù)組：（0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610）。數(shù)組的長(zhǎng)度為16.跳躍搜索將以下列步驟找到55，假設(shè)要跳過(guò)的塊大小為4.?

• 步驟1：從索引0跳轉(zhuǎn)到索引4;?
• 步驟2：從索引4跳轉(zhuǎn)到索引8;?
• 步驟3：從索引8跳轉(zhuǎn)到索引16;?
• 步驟4：由于索引16處的元素大于55，因此我們將返回一步到索引9.?
• 步驟5：從索引9執(zhí)行線性搜索以獲取元素55。

要跳過(guò)的最佳塊大小是多少？
在最壞的情況下，我們必須進(jìn)行n / m跳轉(zhuǎn)，如果最后一個(gè)檢查值大于要搜索的元素，則對(duì)線性搜索進(jìn)行m-1比較。因此，最壞情況下的比較總數(shù)將為（（n / m）+ m-1）。當(dāng)m =√n時(shí)，函數(shù)（（n / m）+ m-1）的值將是最小值。因此，最好的步長(zhǎng)是m =?√n。

?

// C++ program to implement Jump Search #include <bits/stdc++.h> using namespace std;int jumpSearch(int arr[], int x, int n) {// Finding block size to be jumpedint step = sqrt(n);// Finding the block where element is// present (if it is present)int 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 foundif (arr[prev] == x)return prev;return -1; }// Driver program to test function 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]);// Find the index of 'x' using Jump Searchint index = jumpSearch(arr, x, n);// Print the index where 'x' is locatedcout << "\nNumber " << x << " is at index " << index;return 0; }// Contributed by nuclode

輸出：

Number 55 is at index 10

時(shí)間復(fù)雜度：O（√n）
輔助空間：O（1）

注意：

• 該查找只針對(duì)已經(jīng)排序的數(shù)組。
• 要跳過(guò)的塊的最佳大小是O（√n）。這使得跳躍搜索O（√n）的時(shí)間復(fù)雜度。
• 跳躍搜索的時(shí)間復(fù)雜度在線性搜索（（O（n））和二進(jìn)制搜索（O（Log n））之間。
• 二進(jìn)制搜索比跳躍搜索更好，但跳轉(zhuǎn)搜索具有我們僅遍歷一次的優(yōu)點(diǎn)（二進(jìn)制搜索可能需要最多為0（Log n）跳轉(zhuǎn)），考慮要搜索的元素是最小元素或小于最小的）。因此，在跳回成本高昂的系統(tǒng)中，我們使用Jump Search。

轉(zhuǎn)載于:https://www.cnblogs.com/wongyi/p/7729755.html

總結(jié)

以上是生活随笔為你收集整理的跳跃搜索的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。