二分查找

二分查找也叫折半查找，采用此方法时，数据必须是有序的，有效的提高了查找的效率。

主要思想：

    I. 假设查找的数组为array[ left, right ]区间考虑左闭右闭。

1.首确定数组的中间位置mid并记录下来。

2.查找过程有三种情况：

           a.将查找的X值与array[ mid ]比较，如果相等，则返回mid的下标查找成功。

           b.X值小于array[ mid ],则将array[ left ]移至array[ mid - 1 ]，将区间缩小了一半，达到了提高效率的目的。

           c.X值大于array[ mid ],则将array[ right ]移至array[ mid + 1 ]，效果同上。

参考代码如下：

int BinarySearch(int* array, int size, int x) { int right = 0; //考虑区间为左闭右闭的情况 int left = size - 1; //考虑区间为左闭右闭的情况 while(left <= right) { int mid = (left + right)/2; if(mid == x) { return mid; }else if(x < mid) { right = mid - 1; }else if(x > mid) { left = mid + 1; } return -1; } }

   II.array[ left, right）区间考虑左开右闭。

思路与上述相同，只是此时while进入循环的条件应为left < right(考虑难道查找最后一个元素是否可以进入循环)。

参考代码如下：

int Binarysearch(int* array, int size, int x) { int right = 0; //左闭右开的情况 int left = size; //左闭右开的情况 while(right < left) { int mid = (left + right)/2; if(mid == x) { return mid; }else if(x < mid) { left = mid - 1; }else if(x > mid) { right = mid + 1; } return -1; } }

现在的代码看似没有问题，但是考虑到求中间值时 left+right 过大会发生溢出。更加稳妥的情况下，运用下面代码求中间值：

int mid = right + (left - right)>>2;

以上便是二分查找的简单实现。