5 对一艘走私船的二分搜索（第3/3页）

这看起来并不是很多的信息，但是它足够让我们的搜索更加高效。

二分搜索算法的工作原理是：不断地将搜索空间分成两半，并且把搜索空间限制在其中的一半中。这个算法通过改变上下界限有效地限制了搜索空间。上界（IndexHigh）标记了搜索空间有效数组中最高的索引，下界（IndexLow）标记了搜索空间有效数组中最低的索引。通过这个算法，如果目标值在这个数组中，就可以保证：

在搜索的每一步中，我们只需依次判定上界和下界中间的值：

接下来，我们将中间值A[IndexMid]和目标值v进行比较。如果中间值小于目标值（A[IndexMid]<v），我们就知道目标值一定介于这个中间值之后。这样我们可以将IndexLow改为IndexMid+1来使搜索空间又变成原来的一半。

如果中间值比目标值大（A[IndexMid]>v），我们就知道目标一定位于中间值之前，于是我们将IndexHigh改为IndexMid-1来使得搜索空间变成原来的一半。

当然，如果我们发现A[IndexMid]等于v，我们可以直接结束搜索，找到目标值。

现在我们就来使用二分搜索在下面这个已排序的数组中寻找到15。虚线框出的方块是算法当前需要判定的值，而被阴影遮住的部分则是在搜索中被排除的部分。

第一个被判定的中点的值是11，比我们的目标值15小。因为我们知道这个数组是按照升序排列的，所以可以排除中点及其之前的所有部分。我们将下界索引移动到适当的地方（IndexLow=IndexMid+1）。

在第二次比较之后，我们发现中点值是52，比目标值大。我们可以排除中点和它之后的所有部分。此时需要移动我们上界（IndexHigh=IndexMid-1）。

请注意，通过这几次的操作，此时虽然下界已经是目标值了（v=15），但是我们仍需要继续搜索，直到中间值指向目标值。这是因为二分搜索是对中间值进行判定，而不会判定上界和下界是否是目标值。

如果目标值不在数组中会发生什么呢？在搜索过程中，上下界之间的距离会越来越近，直到它们之间没有任何还未检查过的值。因为我们总是将其中一个界限移动到中间值的另一边，所以我们可以在IndexHigh<Indexlow的时候停下来，这个时候就可以保证目标值不在数组中了。