演算法——跳躍搜索

#例如，假設我們有一個大小為n的陣列arr []和區塊（要跳躍）的大小m。然後我們搜尋索引arr [0]，arr [m]，arr [2m] ... ..arr [km]等等。一旦我們找到間隔（arr [km]

我們考慮以下數組：（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跳到索引16;
步驟4：由於索引16處的元素大於55，因此我們將返回一步到索引9.
步驟5：從索引9執行線性搜尋以取得元素55。
要跳過的最佳區塊大小是多少？
在最壞的情況下，我們必須進行n / m跳轉，如果最後一個檢查值大於要搜尋的元素，則對線性搜尋進行m-1比較。因此，最壞情況下的比較總數將為（（n / m） m-1）。當m =√n時，函數（（n / m） m-1）的值將是最小值。因此，最好的步長是m = √n。

// C++ program to implement Jump Search

#include <bits>
using namespace std;

int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);

// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] = n)
return -1;
}

// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] 
<p>輸出：</p>
<p>Number 55 is at index 10</p>
<p>時間複雜度：O（√n）<br>
輔助空間：O（1）</p>
<p><strong>注意：</strong></p>
<p>該尋找只針對已經排序的陣列。 <br>
要跳過的方塊的最佳大小是O（√n）。這使得跳躍搜尋O（√n）的時間複雜度。 <br>
跳躍搜尋的時間複雜度在線性搜尋（（O（n））和二進位搜尋（O（Log n））之間。<br>
二元搜尋比跳躍搜尋更好，但跳轉搜尋具有我們僅遍歷一次的優點（二進位搜尋可能需要最多為0（Log n）跳轉），考慮要搜尋的元素是最小元素或小於最小的）。因此，在跳回成本高昂的系統中，我們使用Jump Search。 </p></bits>

以上是演算法——跳躍搜索的詳細內容。更多資訊請關注PHP中文網其他相關文章！