Lua - 跳跃搜索

Jump Search（跳跃搜索）或 Block Search（块搜索）是一种在已排序列表上进行的搜索算法。它通过以固定大小的步长跳跃，然后在可能包含目标项的块中执行线性搜索来工作。

main.lua

-- 在列表中搜索项的函数
function jump_search(list, item)
   local n = #list  -- 列表的大小
   local step = math.floor(math.sqrt(n)) -- 跳跃的步长
   local prev = 1

   -- 找到可能包含项的块
   while prev < n and list[math.min(step, n)] < item do
      prev = step
      step = step + math.floor(math.sqrt(n))
   end

   -- 在块中执行线性搜索
   while prev <= math.min(step, n) do
      if list[prev] == item then
         return prev
      end
      prev = prev + 1
   end
   return nil -- 如果未找到项则返回 nil
end

-- 示例用法
local numbers = {1, 2, 4, 5, 8, 9}
local item = 8
local index = jump_search(numbers, item)
if index then
   print("Item", item, "found, index:", index) -- 输出: Item 8 found at index: 3
else
   print("Item", item, "not found in the list.")
end

item = 3
index = jump_search(numbers, item)
if index then
   print("Item", item, "found at index:", index)
else
   print("Item", item, "not present.") -- 输出: Item 3 not found in the list.
end

输出

运行上述程序时，我们将得到以下输出−

Item	8	found, index:	3
Item	3	not present.

跳跃搜索的工作原理

• 初始化步长 − 我们将步长初始化为 &sqrt;n，其中 n 是项的数量。

• 计算块 − 现在我们按照块大小（&sqrt;n）递增步长，跳过小于要搜索项的数字。

• 迭代子列表 − 使用线性搜索剩余的项。

• 未找到 − 如果遍历了整个列表仍未找到项，则返回 nil。

时间复杂度

• 最坏情况、最佳情况和平均情况 O(&sqrt;n) − 其中 n 是元素数量。基于跳跃步长的计算来跳跃块。

空间复杂度

• O(1) − 跳跃搜索的空间复杂度是常数，因为它不需要从列表中额外分配内存用于临时存储。

何时使用跳跃搜索

跳跃搜索非常高效，并在以下领域中使用 −

• 当列表已排序时。

• 当访问元素代价较高时，因为跳跃搜索相比二分搜索跳跃次数更少。