most common edition:

1
2
3
4
5
6
7
8
9
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 (key < nums[mid]) high = mid - 1; 
		else low = mid + 1;
	}
	return low;
}

Achtung:

  1. high = mid - 1, low = mid + 1, mid = low + (high - low) / 2, 两头取的是闭区间，求中位数也防止了溢出
  2. 结条件为搜索空间为空，也就是low>high

实际上是一个维护low的过程:low为0开始，只在中位数遇到确定小于目标时才前进，并且永不后退。low一直朝着第一个目标的位置接近，直到到达。

上面代码好用的前提条件: 没有重复值

如果有重复值的话，那么返回的位置就不一定是哪个了，虽然也是目标的位置，但是这个时候我们往往会要求返回第一个大于等于目标值的位置。

那么具体该怎么办呢？其实很简单，当取到等于目标值的时候，之前是直接return，现在我们改为继续减小high来缩小搜索空间。代码如下：

1
2
3
4
5
6
7
8
9
10
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;
}