二分查找法（C++实现）
二分查找法的思想非常简单，在一组已经完成排序的数据(array[])中，如果需要查找某一特定数据（value）是否存在的时候，设置两个上下限（max， min）开始的时候在数组的最前和最后，把需要查找的值跟这两个位置的中间位置数据(array[(max+min)/2])进行对比，如果value >array[(min+max)/2] ,则缩小范围使得min=(min+max)/2,反之，如果value<array[(min+max)/2],则缩小范围使得max=(min+max)/2。持续缩小范围，知道找到对应的值的位置或者min==max,也就是数组中不存在该值。
简单的示例如下：
使用C++代码实现如下：
template <typename T>
int binary(T arr[], int size, T value)
{
if(arr==nullptr || size==0) return -1;
int min=0, max=size-1;
int mid = (max+min)/2;
while(max >= min)
{
if(value == arr[mid]) return mid;
else if(value > arr[mid])
{
min=mid+1;
}
else
{
max=mid-1;
}
mid=(max+min)/2;
std::cout<< "max: "<<max<<" min: "<<min<<std::endl;
}
return -1;
}
这里需要注意的是，在判断了value和中间值的之后，min=mid+1,或者max=mid-1。因为中间值已经判断过不为查找的值，所以+1 -1不会造成漏掉数据。但是如果直接赋值为mide的话，如果查找一个超界的数值的时候，会造成死循环。
二分查找也可以使用递归的方法来实现：
template<typename T>
int find_value(T arr[], int min, int max, T value)
{
std::cout<<"min: "<<min<<" max: "<<max<<std::endl;
if(arr == nullptr || min>max) return -1;
int mid = (min+max)/2;
if(arr[mid] == value) return mid;
else if(arr[mid] > value)
{
return find_value(arr, min, mid-1, value);
}
else if(arr[mid] < value)
{
return find_value(arr, mid+1, max, value);
}
}
再来看一下二分查找的时间复杂度
假设总的数据量为n，每一次二分过后，剩下的数据量为之前的数据量的一般，也就是k此二分之后，数据量为n/2^k，最坏的时间复杂度为n/2^k=1, 也就是logn。其实当数据量很庞大的时候，二分查找的速度非常的快。但是前提是这个方法需要的是一组排序好的数组，所以如果数据量大到几个G的时候并不合适，会占用太大的内存。
