二分查找：
引用网上大神的一句话：
Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky...
这句话可以这样理解：思路很简单，细节是魔鬼。
所以本文中讲述的都是二分查找的细节问题。
定义
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
算法要求
1.必须采用顺序存储结构。
2.必须按关键字大小有序排列。
查找条件
查找区域的左边界，小于等于查找区域的右边界
查找过程
1. 循环条件 == 查找条件
2.计算序列中间下标位置
3.如果待查找值value == 中间位置的元素的值 返回当前中间位置下标
4.如果待查找值value > 序列中间位置元素的值 左边界等于中间位置+1
5.如果带查找值value < 序列中间位置元素的值 右边界等于中间位置-1
6.如果循环结束 返回 -1 (也就是没查找到，返回-1)
用英语作文的写作方式总领一下流程：
First,来说明一下二分查找的具体流程,先说明的是mid中间值的问题：
为什么不用mid = (left+right)/2 ？
因为我们假设定义的类型是int型，查找的是[0,65535]数字中的60000，第一查找mid = (left+right)/2,就会超出int型的数据范围，这样mid值就是内存中的一个不确定数字，但这个数字和我们原来实际查找的中间数是不同的，所以说，这种写法有问题。
正确写法：
int mid = left + ((right-left)>>1);
其中((right-left)>>1)是右值减去左值除2的意思，猛的一看不好理解，举个例子，假设right-left的值为4，二进制就是0100，右移一个就是010，也就是除2的后的值，但为什么是这样写呢？如下，3和5都是不同的形状大小，相减后在平分，也就是中间值的思想。画图理解：
Second,说明的是while()循环括号中两种情况，因为while循环中不同条件影响后面的代码：
这里面的size是数组元素的总大小 。
情况一 int left = 0； int right = size - 1；
这种情况左右都是闭区间，left <= right ,原因如下：
假设我们要找的数字是9，第一次二分查找后，9比5大left = ++mid,right不变，结果是:
注意，我们要找的数字是9，如果left < right,此时循环会跳出，找不到数字9，所以这种情况下是while(left <= right)
Third,关于中间值arr[mid]和要查找的值大小相关的细节问题。
if第一次查找的值比中间值5大，那下一次的查找区间到底要不要包含5呢？答案是不需要。因为第一次查找的时候包含5了,5不是我们想要的查找的数，为了避免重复查找, left = mid + 1
else第一次查找的值比中间值5小，这次变的是右边，right = mid - 1
Finally,情况一 代码如下：
int binarysearch(int arr[], int data, int size)
{
int left = 0;
int right = size - 1;
while (left <= right)
{
int mid = left + ((right - left) >> 1);
if (data == arr[mid])
return mid;
else if (data < arr[mid])
right = mid - 1;
else
left = mid + 1;
}
return -1;
}
情况二 int left = 0; int right = size;
First,开始还是讨论while(),中括号里面的左右比较，这次范围是left < right,因为这次右边的范围是开区间，所以不需要再加上等号，否则在查找的过程中会产生越界的情况。
Secong,中间值的情况和情况一样，都是mid = left + ((right - left) >> 1)
Third,关于中间值arr[mid]和要查找的值大小相关的细节问题。
if查找的值比中间值小，因为右边是开区间，所以这次right = mid
而不是right = mid - 1,如下图所示，如果是mid -1,则在下一次查找中就会漏掉4这个值，因为右边是开区间。
else查找的值比中间值大，因为左侧是闭区间，所以left = mid + 1
Finally,情况二代码如下
int binarysearch(int arr[], int data, int size)
{
int left = 0;
int right = size;
while (left < right)
{
int mid = left + ((right - left) >> 1);
if (data == arr[mid])
return mid;
else if (data < arr[mid])
right = mid;
else
left = mid + 1;
}
return -1;
}
二分查找的复杂度：
总体思路就是每次减半，如图：
计算过程：