二分查找是一种非常简单易懂的快速查找算法，生活中随处可见，比如数字炸弹游戏。
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为0。
惊人的查找速度
二分查找是一种非常高效的查找算法，时间复杂度是O(logn)。
假设数据大小是n，每次查找后数据都会缩小为原来的一半，也就是除以2。最坏情况下，直到查找区间被缩小为空，才停止。
区间大小变化
可以看出这是一个等比数列，其中n/2^k=1时，k就是总共缩小的次数，求得k=log2(n)，所以时间复杂度是O(logn)。
代码实现
非递归实现：
public int Find(int[] datas, int value)
{
if (datas == null || datas.Length == 0) return -1;
int start = 0, end = datas.Length - 1;
int mid;
while (start <= end)
{
mid = start + (end - start) / 2;
if (value == datas[mid])
{
return mid;
}
else if (value < datas[mid])
{
end = mid - 1;
}
else
{
start = mid + 1;
}
}
return -1;
}
递归实现：
public int FindByRecursion(int[] datas, int value)
{
return FindInternallyByRecursion(datas, value, 0, datas.Length - 1);
}
private int FindInternallyByRecursion(int[] datas, int value, int start, int end)
{
if (datas == null || datas.Length == 0) return -1;
if (start > end) return -1;
int mid = start + (end - start) / 2;
if (value == datas[mid])
{
return mid;
}
else if (value < datas[mid])
{
end = mid - 1;
return FindInternallyByRecursion(datas, value, start, end);
}
else
{
start = mid + 1;
return FindInternallyByRecursion(datas, value, start, end);
}
}
二分查找容易出错的地方
1.循环退出条件
注意是low<=high，而不是low<high。
2.mid的取值
mid=(low+high)/2有可能溢出，改进方法是mid=low+(high-low)/2，进一步改为mid=low+((high-low)>>1)。
3.low和high的更新
low=mid+1, high=mid-1。注意这里的+1和-1，写成low=mid或者high=mid，就可能会发生死循环。
二分查找应用场景的局限性
- 二分查找依赖的是顺序表结构，简单点说就是数组。
- 二分查找针对的是有序数组。
- 数据量太小不适合二分查找。
- 数据量太大也不适合二分查找。
二分查找的变体
二分查找虽然原理极其简单，但是想写出没有Bug的二分查找并不容易。
下面介绍四种常见的二分查找变形问题：
变体一：查找第一个值等于给定值的元素
/**
* 查找第一个值等于给定值的元素
*/
public int FindFirst(int[] datas, int value)
{
if (datas == null || datas.Length == 0) return -1;
int start = 0, end = datas.Length - 1;
int mid;
while (start <= end)
{
mid = start + (end - start) / 2;
if (value < datas[mid])
{
end = mid - 1;
}
else if (value > datas[mid])
{
start = mid + 1;
}
else
{
if ((mid == 0) || (datas[mid - 1] != value)) return mid;
else end = mid - 1;
}
}
return -1;
}
变体二：查找最后一个值等于给定值的元素
/**
* 查找最后一个值等于给定值的元素
*/
public int FindLast(int[] datas, int value)
{
if (datas == null || datas.Length == 0) return -1;
int start = 0, end = datas.Length - 1, n = datas.Length;
int mid;
while (start <= end)
{
mid = start + (end - start) / 2;
if (value < datas[mid])
{
end = mid - 1;
}
else if (value > datas[mid])
{
start = mid + 1;
}
else
{
if ((mid == n - 1) || (datas[mid + 1] > value)) return mid;
else start = mid + 1;
}
}
return -1;
}
变体三：查找第一个大于等于给定值的元素
/**
* 查找第一个值大于等于（不小于）给定值的元素
*/
public int FindFirstNotLessThan(int[] datas, int value)
{
if (datas == null || datas.Length == 0) return -1;
int start = 0, end = datas.Length - 1;
int mid;
while (start <= end)
{
mid = start + (end - start) / 2;
if (value <= datas[mid])
{
if ((mid == 0) || (datas[mid - 1] < value)) return mid;
end = mid - 1;
}
else
{
start = mid + 1;
}
}
return -1;
}
变体四：查找最后一个小于等于给定值的元素
/**
* 查找最后一个值大于等于（不小于）给定值的元素
*/
public int FindLastNotMoreThan(int[] datas, int value)
{
if (datas == null || datas.Length == 0) return -1;
int start = 0, end = datas.Length - 1, n = datas.Length;
int mid;
while (start <= end)
{
mid = start + (end - start) / 2;
if (value < datas[mid])
{
end = mid - 1;
}
else
{
if ((mid == n - 1) || (datas[mid + 1] > value)) return mid;
start = mid + 1;
}
}
return -1;
}
