Lua - 二分查找

二分查找是一种非常流行且高效的搜索算法。但在使用二分查找之前，列表必须是已排序的。二分查找算法通过将列表分成两半来工作。如果中间元素与要搜索的项目相同，则搜索完成。否则，如果项目小于中间元素，则在第一半中搜索；如果项目大于中间元素，则在第二半中搜索。

main.lua

-- 在列表中搜索项目的函数
function binary_search(list, item)
   local low = 1 
   local high = #list 

   -- 循环直到 low 变得与 high 相同或更高
   while low <= high do
      local mid = math.floor((low + high) / 2)  -- 计算中间索引
      if list[mid] == item then   -- 如果找到项目
         return mid -- 返回项目的索引
      elseif list[mid] < item then  -- 如果项目大于中间项目
         low = mid + 1 -- 在右半部分执行搜索
      else
         high = mid - 1 -- 在左半部分执行搜索
      end
   end
   return nil -- 如果未找到项目则返回 nil
end

-- 示例用法
local numbers = {1, 2, 4, 5, 8, 9}
local item = 8
local index = binary_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 = binary_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.

二分查找的工作原理

• low 和 high − 我们将 low 初始化为 1，high 初始化为列表长度，作为初始列表索引。循环运行直到 low 变得与 high 相同或更高。

• 将列表分成两半 − 计算中间点，并检查中间项目。如果找到，则返回索引。

• 迭代子列表 − 在计算 low 和 high 后，对子列表重复上述步骤。

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

时间复杂度

• 最坏情况 O(log n) − 其中 n 是元素数量。如果项目不存在，每次搜索都会将搜索范围减半。

• 最好情况 O(1) − 项目是列表的中间元素。

• 平均情况 O(log n) − 二分查找在每次迭代中将待搜索项目减半。

空间复杂度

• O(1) − 二分查找的空间复杂度是常数，因为它不需要从列表中额外分配内存用于临时存储。在递归实现的情况下，由于需要调用栈，它是 O(log n)。

何时使用二分查找

二分查找非常高效，常用于以下领域 −

• 当列表已排序时。

• 当需要对大型已排序数据集使用高效算法时。