前言
二分查找算是最经典也最入门的算法了，大一新生刚学C语言就开始写，但是看似简单的二分算法，想要考虑周全写得完美也是要费点功夫。
比如java库里的二分查找，一个溢出的bug还存在了很久，更有号称90％程序员写不出无BUG的二分查找程序，夸张了。。。
自我分析
先来看看我平时最喜欢用的二分查找代码
int binarysearch(int nums[], int low, int high, int key){
while(low<=high){
int mid = low + (high - low) / 2;
if(nums[mid] == key)
return mid;
else if(nums[mid]>key)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
这里面几个注意的点：
- 我老老实实取的两头闭区间，求中位数也防止了溢出
- 终结条件为搜索空间为空，也就是low>high
- 返回值完全不需要纠结，直接返回低位 low，当然除非要求找不到返回-1
慢放整个搜索过程，实际上是一个维护low的过程：
low为0开始，只在中位数遇到确定小于目标时才前进，并且永不后退。low一直朝着第一个目标的位置接近，直到到达。
这代码一直用的挺好的，但其实有一个前提条件：没有重复值
如果有重复值的话，那么返回的位置就不一定是哪个了，虽然也是目标的位置，但是这个时候我们往往会要求返回第一个大于等于目标值的位置。
那么具体该怎么办呢？其实很简单，当取到等于目标值的时候，之前是直接return，现在我们改为继续减小high来缩小搜索空间。代码如下：
int binarysearch_lower_bound(int nums[], int low, int high, int key){
while(low<=high){
int mid = low + (high - low) / 2;
if(nums[mid]>=key)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
其实这就对应C++里的lower_bound()函数了
Classical Code
参考 ClassicalCode/BinarySearch.cpp
上面的版本区间为左闭右开，且边界条件改为while(lo < hi)，对应的hi = mid ;我还不怎么适应，下面给出我的版本（左右闭区间）以及递归实现
//二分查找之找到nums[lo, hi]大于等于key值的第一个元素位置
int binarysearch_lower_bound(int nums[], int low, int high, int key){
while(low<=high){
int mid = low + (high - low) / 2;
if(nums[mid]>=key)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
//递归版本
int binarysearch_firstoccur(int nums[], int low,int high, int key){
if (low > high)
return low;
int mid = low + (high - low) / 2;
if(nums[mid]>=key)
return binarysearch_firstoccur(nums, low, mid-1, key);
if(nums[mid] < key)
return binarysearch_firstoccur(nums, mid + 1, high, key);
}
//二分查找之找到严格大于key值的第一个元素
int binarysearch_upper_bound(int nums[], int low, int high, int key){
while(low<=high){
int mid = low + (high - low) / 2;
if(nums[mid]>key)
high = mid - 1;
else
low = mid + 1;
}
return low;
}
