1. 在数组中查找（Searching in an Array）¶
1.1. 在数组中查找¶
1.1.1. 顺序查找（Sequential Search）¶
如果你想在包含 \(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
}
// Find the position in A that holds value K, if any does
int sequential(int A[], int size, int K) {
for (int i=1; i<size; i++) // For each element
if (A[i] == K) // if we found it
return i; // return this position
return size; // Otherwise, return the array length
}
自然而然会问一个程序或算法运行 需要多长时间。 但我们实际上并不关心某个特定的程序在 某台特定的计算机上要运行多久。 我们只想要某种估算，让我们可以把求解一个问题的 一种方法与另一种方法进行比较。 这就是 算法分析 的基本思想。 就顺序查找而言，很容易看出如果该值 在数组的第 \(i\) 个位置上，那么顺序查找 要查看 \(i\) 个值才能找到它。 如果该值根本不在数组中，那么如果数组有 \(n\) 个值， 我们就必须查看 \(n\) 个值。 这被称作顺序查找的 最坏情况。 由于工作量与 \(n\) 成正比， 我们说顺序查找的最坏情况具有 线性开销。 因此，顺序查找算法有时 被称为 线性查找。
1.1.2. 二分查找（Binary Search）¶
顺序查找是在未排序数组中查找 值时我们可以做到的最好的了。 [1] 但如果数组按值升序排序，我们就可以 做得好得多。 我们使用一个称为 二分查找 的过程。
二分查找首先要检查数组的中间 位置的值；把这个位置称为 \(mid\)，把 对应的值称为 \(k_{mid}\)。 如果 \(k_{mid} = K\)，那么处理可以立即停止。 然而，这种情况不太可能发生。 幸运的是，知道中间值提供了有用的信息， 可以帮助引导查找过程。 特别是，如果 \(k_{mid} > K\)，那么你就知道值 \(K\) 不可能出现在数组中任何大于 \(mid\) 的位置。 因此，你可以排除对数组上半部分的后续查找。 相反，如果 \(k_{mid} < K\)，那么你就知道可以 忽略数组中所有小于 \(mid\) 的位置。 无论哪种情况，一半的位置都被排除在进一步 的考虑之外。 二分查找接着看向可能存在的值 \(K\) 所在的那部分 数组的中间位置。 这个位置的值再次让我们从考虑中排除剩下的一半 位置。 这个过程不断重复，直到要么找到期望的值，要么 数组中没有剩余的位置可能包含 值 \(K\)。 这里是对二分查找方法的说明。
借助正确的数学技巧，不难证明 二分查找在 \(n\) 个值的数组上的开销最多是 \(\log n\)。 这是因为我们反复把必须查看的子数组 的大小劈成两半。 （在最坏情况下）我们在到达大小为 1 的子数组时停止。 而在我们到达 1 之前，我们只能把 \(n\) 的值 削减 \(\log n\) 次。 [2]
