10.5.1.1. 顺序查找¶

若要在存放 \(n\) 个整数的无序数组中找出某个特定值所在的位置，最直接的办法就是从数组开头往后逐个查找，直到找到目标为止——基本上没有比这更好的办法了。这种算法称为 顺序查找。如果找到了目标，就称之为 成功查找；如果目标不在数组中，最终会一直查到末尾，这称为 不成功查找。下面是顺序查找的一个简单实现。

// Return the position of an element in array A with value K.
// If K is not in A, return A.length.
static int sequential(int[] A, int K) {
  for (int i=0; i<A.length; i++) // For each element
    if (A[i] == K)               // if we found it
       return i;                 //   return this position
  return A.length;               // Otherwise, return the array length
}

// Return the position of an element in array A with value K.
// If K is not in A, return A.length.
static int sequential(int[] A, int K) {
  for (int i=0; i<A.length; i++) { // For each element
    if (A[i] == K) {               // if we found it
       return i;                 //   return this position
    }
  }
  return A.length;               // Otherwise, return the array length
}

人们自然想知道一个程序或算法要运行多久。但我们并不真的关心某个程序在某台具体计算机上确切运行多长时间，我们只需一个大致估算，以便比较解决同一问题的不同方法。这正是 算法分析 的基本思想。就顺序查找而言，容易看出：如果目标位于数组的第 \(i\) 个位置，那么顺序查找需要查看 \(i\) 个值才能找到它；如果目标根本不在数组中，而数组有 \(n\) 个值，那就必须查看全部 \(n\) 个值。这就是顺序查找的 最坏情况。由于工作量与 \(n\) 成正比，我们说顺序查找的最坏情况具有 线性开销。正因如此，顺序查找有时也称为 线性查找。

10.5.1.2. 二分查找¶

在无序数组中查找某个值时，顺序查找已经是我们所能做到的最好办法了。 [1] 但如果数组按值递增有序，我们就能做得更好，所用的方法称为 二分查找。

二分查找先检查数组中间位置的值；把这个位置记作 \(mid\)，对应的值记作 \(k_{mid}\)。如果 \(k_{mid} = K\)，处理就可以立即结束——不过这种情况很少出现。幸运的是，中间值提供了有用的信息，可以引导后续查找：具体来说，如果 \(k_{mid} > K\)，那么 \(K\) 不可能出现在大于 \(mid\) 的任何位置上，于是数组的上半部分可以全部排除；反之，如果 \(k_{mid} < K\)，那么小于 \(mid\) 的所有位置都可以忽略。无论哪种情况，都排除掉了一半的位置。接下来，二分查找在 \(K\) 可能出现的那个半区里，再次查看其中间位置，同样又能排除剩余位置的一半。如此反复，直到找到目标值，或数组中已没有任何位置可能包含 \(K\) 为止。下图演示了二分查找的方法。

Settings

Saving...
Server Error
Resubmit

用恰当的数学方法不难证明：在含 \(n\) 个值的数组上，二分查找的成本至多为 \(\log n\)。这是因为我们一次次把待查子数组的规模减半；最坏情况下，当子数组缩小到规模 1 时停止，而要把 \(n\) 反复减半到 1，最多只能减半 \(\log n\) 次。 [2]