跳躍搜尋

1. 跳躍搜尋演算法
2. 跳躍搜尋示例
3. 跳躍搜尋演算法的實現
4. 跳躍搜尋演算法的複雜度

跳躍搜尋是一種區間搜尋演算法。它是一種相對較新的演算法，只適用於排序陣列。它試圖比線性搜尋減少所需的比較次數，不像線性搜尋那樣掃描每一個元素。在跳躍搜尋中，陣列被分成 m 塊。它搜尋一個塊中的元素，如果該元素不存在，則移動到下一個塊。當演算法找到包含元素的塊時，它使用線性搜尋演算法來尋找精確的索引。這種演算法比線性搜尋快，但比二叉搜尋慢。

跳躍搜尋演算法

假設我們有一個未排序的陣列 A[]，包含 n 個元素，我們想找到一個元素 X。

跳躍搜尋示例

假設我們有一個陣列：(1, 2, 3, 4, 5, 6, 7, 8, 9)，我們想找到 X-7。

因為有 9 個元素，所以我們把 n 設為 9。

跳躍搜尋演算法的實現

#include <bits/stdc++.h>
using namespace std;

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

    int m = sqrt(n);
    int i = 0;
    while (arr[min(m, n) - 1] < x)
    {
        i = m;
        m += sqrt(n);
        if (i >= n)
            return -1;
    }
    while (arr[i] < x)
    {
        i++;
        if (i == min(m, n))
            return -1;
    }
    if (arr[i] == x)
        return i;

    return -1;
}

int main() {
    int n = 10;
    int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    int x = 7;
    int result = jumpSearch(arr, x, n);
    if (result == -1) cout << "Element not found";
    else cout << "Element found at index " << result;
}

跳躍搜尋演算法的複雜度

時間複雜度

• 平均情況

跳躍排序演算法執行 n/m 次，其中 n 是元素數量，m 是塊大小。線性搜尋需要 m-1 次比較，使得總時間表示式為 n/m+m-1。使時間表示式最小化的 m 的最優值為√n，使得時間複雜度為 n/√n+√n，即√n。跳躍搜尋演算法的時間複雜度為 O(√n)。

• 最佳情況

最佳情況下的時間複雜度是 O(1)。當要搜尋的元素是陣列中的第一個元素時，就會出現這種情況。

• 最壞情況

最壞的情況發生在我們做 n/m 跳躍的時候，我們最後檢查的值大於我們要搜尋的元素，m-1 比較進行線性搜尋。最壞情況下的時間複雜度為 O(√n)。

空間複雜度

這種演算法的空間複雜度是 O(1)，因為除了臨時變數外，它不需要任何資料結構。