與二分搜索一樣，跳轉(zhuǎn)搜索是一種針對排序數(shù)組的搜索算法?；舅枷胧峭ㄟ^按固定步驟向前跳躍或跳過某些元素來代替搜索所有元素來檢查更少的元素（比線性搜索）。例如，假設我們有一個大小為 n 的數(shù)組 arr[] 和一個大小為 m 的塊（要跳轉(zhuǎn)）。然后我們在索引 arr[0]、arr[m]、arr[2m]…..arr[km] 等中搜索。一旦找到區(qū)間 (arr[km] < x < arr[(k+1)m])，我們就從索引 km 執(zhí)行線性搜索操作來查找元素 x。讓我們考慮以下數(shù)組：(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610)。數(shù)組長度為 16。

假設要跳轉(zhuǎn)的塊大小為 4，跳轉(zhuǎn)搜索將找到值 55，步驟如下：

步驟 1：從索引 0 跳轉(zhuǎn)到索引 4；

步驟2：從索引4跳轉(zhuǎn)到索引8；

步驟3：從索引8跳轉(zhuǎn)到索引12；

步驟 4：由于索引 12 處的元素大于 55，因此我們將跳回到索引 8。

步驟 5：從索引 8 執(zhí)行線性搜索以獲取元素 55。

與線性搜索和二分搜索相比的性能：如果我們將它與線性搜索和二分搜索進行比較，那么它比線性搜索更好，但不比二分搜索更好。

性能遞增順序為：線性搜索 < 跳轉(zhuǎn)搜索 < 二分搜索

要跳過的最佳塊大小是多少？在最壞的情況下，我們必須進行 n/m 次跳轉(zhuǎn)，如果最后檢查的值大于要搜索的元素，我們會為線性搜索多執(zhí)行 m-1 次比較。因此，最壞情況下的總比較次數(shù)將為((n/m) + m-1)。當 m = ?n 時，函數(shù) ((n/m) + m-1) 的值最小。因此，最佳步長為 m = ?n。 

算法步驟

1、跳轉(zhuǎn)搜索是一種通過跳過數(shù)組中的某些步驟來查找已排序數(shù)組中的特定值的算法。
2、步驟由數(shù)組長度的 sqrt 確定。 

以下是跳躍搜索的分步算法：

1、通過取數(shù)組 n 長度的 sqrt 來確定步長 m。
2、從數(shù)組的第一個元素開始，跳 m 步，直到該位置的值大于目標值。

• 一旦找到大于目標的值，就從上一步開始進行線性搜索，直到找到目標或者明確目標不在數(shù)組中。
• 如果找到目標，則返回其索引。如果沒有，則返回 -1 表示在數(shù)組中未找到目標。 

示例：

// 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);
    }
} 

輸出：

數(shù)字 55 位于索引 10
時間復雜度：O(?n) 
輔助空間：O(1)

跳轉(zhuǎn)搜索的優(yōu)點：

1、比元素均勻分布的數(shù)組的線性搜索更好。
2、與大型數(shù)組的線性搜索相比，跳躍搜索的時間復雜度較低。
3、跳躍搜索的步數(shù)與數(shù)組大小的平方根成正比，對于大型數(shù)組來說效率更高。
4、與二分搜索或三元搜索等其他搜索算法相比，它更容易實現(xiàn)。
5、跳轉(zhuǎn)搜索適用于元素有序且均勻分布的數(shù)組，因為它可以在每次迭代時跳轉(zhuǎn)到數(shù)組中更接近的位置。

要點：

1、僅適用于排序數(shù)組。
2、所要跳轉(zhuǎn)的塊的最佳大小是(?n)。這使得跳轉(zhuǎn)搜索的時間復雜度為O(?n)。
3、跳轉(zhuǎn)搜索的時間復雜度介于線性搜索 ((O(n)) 和二分搜索 (O(Log n)) 之間。
4、二分查找比跳轉(zhuǎn)查找要好，但是跳轉(zhuǎn)查找的優(yōu)點是我們只需要回溯一次（二分查找可能需要最多 O(Log n) 次跳轉(zhuǎn)，考慮要查找的元素是最小元素或者更大的元素的情況比最小的）。因此，在二分搜索成本高昂的系統(tǒng)中，我們使用跳轉(zhuǎn)搜索。 

到此這篇關(guān)于java 跳轉(zhuǎn)搜索的實現(xiàn)示例的文章就介紹到這了,更多相關(guān)java 跳轉(zhuǎn)搜索內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論