2.2　有序数组的查找

第1章介绍过在传统数组中查找特定值的过程：从左向右，依次检查每个格子，直至找到这个值。我当时把这个过程叫作线性查找。

下面来看看传统数组和有序数组的线性查找有何区别。

假设我们有一个常规数组[17, 3, 75, 202, 80]。如果要查找一个数组中不存在的值22，则需要检查每个元素，因为22有可能在数组中的任何位置。除非在检查到数组末尾之前就找到这个值，否则只能全部检查一遍。

而对有序数组来说，即便值不在数组中，也能提前结束查找。假设要在有序数组[3, 17, 75, 80, 202]中查找值22，因为22不可能在75右边，所以只需检查到75即可。

有序数组线性查找的Ruby实现如下。

def linear_search(array, search_value)
  # 遍历数组中的每个元素：
  array.each_with_index do |element, index|
    # 如果找到了值，就返回其索引：
    if element == search_value
      return index
    # 如果找到了一个比所查找值大的元素，那么可以提前退出循环：
    elsif element > search_value
      break
    end
  end
  # 如果没有找到所查找的值，则返回nil：
  return nil
end

这种方法有两个参数：array是查找的有序数组，search_value是要查找的值。

要在上面的范例数组中查找22，可以像下面这样调用上面的函数。

p linear_search([3, 17, 75, 80, 202], 22)

如你所见，linear_search方法在寻找search_value时需要遍历数组的每一个元素。当遍历到的element大于search_value时，查找立刻结束。这是因为剩下的数组中不可能含有search_value。

根据这一点，与传统数组相比，有时有序数组的线性查找会少用几步。不过，如果查找一个刚好在数组末尾，甚至根本不在数组中的值时，则还是要搜索每一个格子。

乍一看，标准数组和有序数组的效率没什么区别，或者说至少在最坏情况下没什么区别。如果两种数组都有N个元素，那么线性查找可能都需要最多N步。

但马上要介绍的这个算法，足以把线性查找“扔进历史的垃圾堆”。

目前为止，我们都假定线性查找是在有序数组中搜索一个值的唯一方法。但事实上线性查找只是其中一种算法。它并不是唯一的选择。

与传统数组相比，有序数组的优势就在于可以用另一个查找算法。这就是二分查找，它比线性查找要快得多。