跳躍搜尋

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 跳躍搜尋演算法
  2. 跳躍搜尋示例
  3. 跳躍搜尋演算法的實現
  4. 跳躍搜尋演算法的複雜度
跳躍搜尋

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

跳躍搜尋演算法

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

  • 從第一個元素開始設定 i0,塊大小 m√n
  • A[min(m,n)-1]<Xi<n 時。
    • i 設為 m,並以√n 遞增 m
  • If i >= n return -1
  • A[i]< X 時,執行以下操作。
    • 遞增 i
    • 如果 i 等於 min(m,n) 返回 -1
  • 如果 A[i] == X,返回 i
  • 否則,返回 -1

跳躍搜尋示例

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

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

  • i0m√93
  • A[2]X 小。設 i3m6
  • A[5]X 小。設 i6m9
  • A[8] 等於 X . 突破迴圈。
  • i 作為 6 小於 n
  • A[6] == 7,跳出迴圈。
  • 因為 A[6]=7,所以返回 6

跳躍搜尋演算法的實現

#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),因為除了臨時變數外,它不需要任何資料結構。

Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

相關文章 - Search Algorithm