2.2 查找有序数组

上一章介绍了常规数组的查找方式：从左至右，逐个格子检查，直至找到。这种方式称为线性查找。

接下来看看有序数组的线性查找跟常规数组有何不同。

设一个常规数组[17,3,75,202,80]，如果想在里面查找22（其实并不存在），那你就得逐个元素去检查，因为22可能在任何一个位置上。要想在到达末尾之前结束检查，那么所找的值必须在末尾之前出现。

然而对于有序数组来说，即便它不包含要找的值，我们也可以提早停止查找。假设要在有序数组[3,17,75,80,202]里查找22，我们可以在查到75的时候就结束，因为22不可能出现在75的右边。

以下是用Ruby语言实现的有序数组线性查找。

        def linear_search(array, value)

          # 遍历数组的每一个元素
          array.each do |element|

            # 如果这个元素等于我们要找的值，则将其返回
            if element==value
              return value

            # 如果这个值大于我们要找的值，则提早退出循环
            elsif element > value
              break
            end
          end

          # 如果没找到，则返回空值
          return nil
        end

因此，有序数组的线性查找大多数情况下都会快于常规数组。除非要找的值是最后那个，或者比最后的值还大，那就只能一直查到最后了。

只看到这里的话，可能你还是不会觉得两种数组在性能上有什么巨大区别。

这是因为我们还没释放算法的潜能。这是接下来就要做的。

至今我们提到的查找有序数组的方法就只有线性查找。但其实，线性查找只不过是查找算法的其中一种而已。这种逐个格子检查直至找到为止的过程，并不是查找的唯一途径。

有序数组相比常规数组的一大优势就是它可以使用另一种查找算法。此种算法名为二分查找，它比线性查找要快得多。