延續猜數字遊戲，1 ~ 100 我們是不是可以換個猜法呢？
如果我們從一開始，只要每次沒猜中，我們就往後面 +10 繼續猜，直到最大值範圍值變成我們所猜的數值後，往回開始找值，這樣做，在數值較小的時候，將會更有效率。
概念
跳躍搜尋 (Jump Search)： 這個演算法很像二元搜尋法，被搜尋的清單也是需要事先，先被排序過的，但是在每次查找的過程，如果找不到值，就用一個基值快速地跳到下一個區段查找，直到最大值被變小，再往回開始找值，如果有找到就會回傳元素索引值，否則就會回傳 -1。
上面的敘述可能會有點複雜，以數猜數字為例，假設現在要查找的數值是 30：
- Step 1: index = 1 ，目標數值並不等於 1 ，先將索引 +10。
- Step 2: index = 11，目標數值並不等於 11，再將索引 +10。
- Step 3: index = 21，目標數值並不等於 21，再將索引 +10。
- Step 4: index = 31，目標數值並不等於 31，但是發現要找數值比 31 還小，所以要開始往回找，將索引 -1。
- Step 5: index = 30，發現目標索引為 30，回傳索引值。
複雜度
- 時間複雜度： O(√n)
- 空間複雜度： O(1)
範例
Go
package main
import (
"fmt"
"math"
)
func jumpSearch(list []int, target int) int {
blockSize := int(math.Sqrt(float64(len(list))))
i := 0
for {
if i > len(list) {
return -1
}
if list[i] >= target {
break
}
i += blockSize
}
for j := i; j > 0; j-- {
if list[j] == target {
return j
}
}
return -1
}
func main() {
fmt.Println(jumpSearch([]int{1, 2, 3, 4, 5}, 3)) // 2
fmt.Println(jumpSearch([]int{1, 2, 3, 4, 5}, 6)) // -1
}
C#
class Algorithm
{
public static int jumpSearch(int[] list, int target)
{
var blockSize = (int)Math.Sqrt(list.Length);
var i = 0;
while (true)
{
if (i > list.Length)
{
return -1;
}
if (list[i] >= target)
{
break;
}
i += blockSize;
}
for (var j = i; j > 0; j--)
{
if (list[j] == target)
{
return j;
}
}
return -1;
}
public static void Main(String[] args)
{
Console.WriteLine(jumpSearch(new int[] {1, 2, 3, 4, 5}, 3)); // 2
Console.WriteLine(jumpSearch(new int[] {1, 2, 3, 4, 5}, 6)); // -1
}
}
歡迎到我的 Facebook Alan 的筆記本 留言，順手給我個讚吧！你的讚將成為我持續更新的動力，感謝你的閱讀，讓我們一起學習成為更好的自己。