Ruby实现二分搜索(二分查找)算法的简单示例

在计算机科学的世界里，二分搜索（Binary Search）是个经典到不能再经典的算法，也叫折半搜索、对数搜索。它的任务很简单：在一个有序数组中，快速找到某个特定元素。怎么找？从数组的中间元素开始下手。如果中间那个恰好就是你要找的，万事大吉；如果目标比中间元素大或小，那就只关注对应的一半区域，继续从中间开始比较。每一步，搜索范围都会缩小一半。直到某一步数组为空，就说明目标不存在。这种“每次比较砍掉一半”的策略，效率相当惊人。

复杂度分析

时间复杂度
折半搜索每次都将搜索区域缩小为原来的一半，因此时间复杂度为 （n 表示集合中元素的个数）。这意味着即使数据量很大，搜索次数也只是对数级别增长。

空间复杂度
虽然算法可以用递归形式来定义，但它本质上是尾递归，完全可以改写成循环来实现，空间开销可以控制在常数级别。

Ruby 代码示例

def binseaech(arr, i)
  low, high = 0, arr.size - 1
  while (low < high)
    mid = (low + high)/2
    if arr[mid] < i
      low = mid + 1
    elsif arr[mid] > i
      high = mid - 1
    else
      return mid
    end
  end
end

arr = [1,3,12,34,35,46,91,108]
puts binseaech(arr, 91)

运行结果：

6
[Finished in 0.1s]

从输出可以看到，元素 91 在数组中的索引是 6（从0开始计数），整个查找过程仅用了0.1秒。二分搜索的简洁与高效，在这里一目了然。