作者 | Cooper Song
责编 | 刘静
出品 | CSDN（ID：CSDNnews）
二分查找也叫折半查找(Binary Search)，是一种时间复杂度为O(logn)，因为它可以每次都将查找范围缩小为原来的一半。它要求查找序列要有序。然而这里所说的“有序”，你真正理解了吗？
数字的二分查找
先描述一下最简单的二分查找算法：
先设返回值为-1，如果找不到的话就返回-1。
设置两个指针，left和right，left最开始指向第一个元素的下标，right最开始指向最后一个元素的下标，每次查找都要找到中间值值的下标mid=(left right)/2，让中间值arr[mid]跟查找值target进行比较。
如果查找值target等于中间值arr[mid]，这说明找到了查找值target，直接返回mid作为查找值target的下标；
如果查找值target小于中间值arr[mid]，这说明查找值target如果存在的话一定位于中间值的左边，因此我们将right置为mid-1，这样下次需要查找的序列就变成了从left到mid-1；
如果查找值target大于中间值arr[mid]，这说明查找值target如果存在的话一定位于中间值的右边，因此我们将left置为mid 1，这样下次需要查找的序列就编程了从mid 1到right。
如此循环，直到left>right结束。
简单二分查找的代码：
int binarySearch(int target)
{
int ret=-1;
int len=arr.size;
int left=0;
int right=len-1;
while(left<=right)
{
int mid=(left right)/2;
if(target==arr[mid])
{
ret=mid;
break;
}
else if(target<arr[mid])
{
right=mid-1;
}
else
{
left=mid 1;
}
}
return ret;
}
看一个最简单的二分查找的例子：
序列：arr=[-2,0,5,9,15,30,32,79]
查找值：target=3
下面开始二分查找，橙色部分为left，黄色部分为right，绿色部分为mid。
