二分法搜索算法

之前说过，二分法算法是一种非常常见的算法。这里大概说说算法的内容。具体算法如果有兴趣，去百度、维基百科，搜搜就都能找到。我就不做搬运工了。这里就我个人的理解，不严谨的说说。

在排序好的一列大小为n的数组A[]，找数字num。设left=0，right=n-1：

while(left<=right){

mid = (left + right)/2;

if (A[mid] == num) return mid;

if (A[mid] < num) left = mid + 1;

if (A[mid] > num) right = mid - 1;

}

return -1;

这里面 mid是我们找的中间点。如果正好找到了，那就直接返回不用继续找了。如果num比中间点的数大，那左边就移动到中间点的右边。这样搜索的范围就小了一半。反之，则把右边移到中间点的左边。

最终如果已经搜素过了整个范围，left已经大于right，我们还没有找到num，那就是这个数组里没有这个数。这里我用一个数组里并不存在的index，-1，来表示。

这个看起来简单，但在实际的实现中，还有很多要注意的地方，这个以后有机会再说。

总之，上面已经给出了了最基本的二分法搜索算法：通过每次重新界定左右边界来缩小一半的搜索范围。