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步。

但馬上要介紹的這個算法，足以把線性查找“扔進歷史的垃圾堆”。

目前為止，我們都假定線性查找是在有序數組中搜索一個值的唯一方法。但事實上線性查找只是其中一種算法。它并不是唯一的選擇。

與傳統數組相比，有序數組的優勢就在于可以用另一個查找算法。這就是二分查找，它比線性查找要快得多。