在微博上看到一篇文章，关于二分查找：当我写二分查找时，我想些什么

于是想到刚看过的《编程珠玑》上的一句话，“90%的人无法正确写出二分查找”

自己动手：

int BinarySearch(int A[], int n, int target)
{
    int left=0, right=n-1;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(A[mid] == target) return mid;
        if(target > A[mid]) left=mid+1;
        else right=mid-1;
    }
    return -1;
}

写完了后，去看这篇文章的答案，发现有很多问题，果然也属于那“90%”。

问题1, 需要对n进行判断，这个属于编程严谨性的问题；第二个问题，程序可以“优化”。

我们先来考虑循环的执行步骤。假设我们有一个有着 n 个元素的数组（此处n是一个很大的数值），那么从该数组中第一次找到目标的概率为 1/n（一个很小的数值），下一次（经过一次二分）的概率则是 1/(n/2)——仍然不是很大——以此类推下去。事实上，只有当元素的个数减少到了 10 到 20 的时候，一次找到目标的概率才变得有意义，而对于10 到 20 个元素进行查找需要的只是大概 4 次循环。当查找失败时（在大多数的应用中很普遍），那些额外的测试就将变成纯粹的额外开销。

我们也可以来计算一下，在什么时候找到目标值的概率能接近 50%，但请你扪心自问：在一个复杂度为 O(log2N) 的算法中，对于它的每一步都增添一个额外的复杂计算，而目的仅仅是为了减少最后的几次计算，这样做有意义吗？

这段话什么意思呢？归根到底就一个意思，如果一个很大的数组中没有我们想要的目标，那么条件判断 if (A[mid] == target) 完全是一个不必要的开销（分支跳转）。实际上，这种条件只要一次就够了，那就是循环终止并判断最终目标的时候。

代码可以改为：

int BinarySearch(int A[], int n, int target)
{
    int left=0, right=n-1;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(target > A[mid]) left=mid+1;
        else right=mid-1;
    }
    if(left>=n || A[left]!=target) return -left-1;
    return left;
}

这里注意上面的return -left-1，这行代码在找不到目标时，将目标合适的插入位置输出了，可谓一举两得。