总结嘛， 直接上代码。
二分有各种各样的理解， 总会有正确或者不正确， 自己摸索之路难又难。（当然我知道是我太菜， 还不努力）
现在我不是很理解， 就直接上代码了， 等着以后理解了在补回来吧。 若有错误一定要指正。

理解（更新于2019年7月29日）

顿悟了顿悟了， 真爽爽。

  1. 基于闭区间[low, high]。
  2. while循环里的条件都是 while(low < high)， 即当 low == high 时退出， 为什么满足这个条件一定是low == high ， 这个下面再说。
  3. 重点重点重点 自己心里要想清楚你要求得是什么， 然后根据你要求得来分析思路。举两个例子：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    //在非递减数组中，  查找最小的比key值大的数的下标。 既然是最小的， 又是非递减数组， 那么正查找肯定是要从前向后查找， 看下面代码分析
    int binary_search(int a[], int low, int high, int key){
        int m;
        while(low < high){
            m = low + (high - low) / 2;  //这里是向下取整， 因为你是从前往后找
            if (a[m] <= key)
                low = m + 1;  // 从前向后， 如果不满足条件的话，所以是改变的low
            else 
                high = m;  // 如果满足条件， high就不变
        }
        if (a[low] > key)  // 如果这个值满足条件
            return low;
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//在非递增数组中，  查找最小的比key值大的数的下标。 既然是最小的， 是非递增数组， 那么正常查找肯定是从后往前查找
int binary_search(int a[], int low, int high, int key){
    int m;
    while(low < high){
        m = low + (high - low + 1) / 2; //向上取整， 因为是从后往前找呀
        if (a[m] > key)  // 如果满足条件， low就不变
            low = m;
        else
            high = m - 1; // 从后往前， 所以改变的是high
    }
    if (a[low] > key)
        return low;
    return -1;
}

现在解决上面那个遗留问题： 从上面两段代码可以看出， 每一次二分完跨度都是1， 所以不会出现从low < high 直接编程low > high 只能是low = high。
看完上面两个例子， 应该就理解的差不多了吧， 要是不理解， 就自己动手， 动手的时候也好动动脑，嘿嘿， 加油吧骚年。
下面是我以前死记硬背的， 就不删了吧， 留作纪念。

以下全都是基于非递减， 闭区间[low, high].

查找key值， 若存在， 返回最左边的下标， 若不存在，返回负一。

1
2
3
4
5
6
7
8
9
10
11
12
13
int binary_search_1(int a[], int low, int high, int key){ // low high 为闭区间
    int m;
    while(low < high){  // 闭区间[low, high]
        m = low + (high - low) / 2;   // 向下取整
        if (a[m] < key)   // 对于非递增区间， 只需把此处换成 >
            low = m + 1;
        else
            high = m;
    }
    if (a[low] == key)
        return low;
    return -1;
}

查找key值， 若存在， 返回最右边的下标， 若不存在，返回负一。

1
2
3
4
5
6
7
8
9
10
11
12
13
int binary_search_2(int a[], int low, int high, int key){ // low high 为闭区间
    int m;
    while(low < high){
        m = low + (high - low + 1) / 2;  // 向上取整
        if (a[m] <= key) // 对于非递增区间， 只需把此处换成 >=
            low = m;
        else
            high = m - 1;
    }
    if (a[low] == key)
        return low;
    return -1;
}

查找最小的比key值大的数的下标， 若不存在， 返回负一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 相当于upper_bound()
int binary_search_3(int a[], int low, int high, int key){ // low high 为闭区间
    int m;
    while(low < high){
        m = low + (high - low) / 2;
        if (a[m] <= key)
            low = m + 1;
        else
            high = m;
    }
    if (a[high] > key)
        return high;
    return -1;
}

查找最大的比key值小的数的下标， 若不存在， 返回负一。

1
2
3
4
5
6
7
8
9
10
11
12
13
int binary_search_4(int a[], int low, int high, int key){ // low high 为闭区间
    int m;
    while(low < high){
        m = low + (high - low + 1) / 2;
        if (a[m] < key)
            low = m;
        else
            high = m - 1;
    }
    if (a[low] < key)
        return low;
    return -1;
}

查找最小的比key值大于等于的数的下标， 若不存在， 返回负一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 相当于lower_bound()
int binary_search_5(int a[], int low, int high, int key){ // low high 为闭区间
    int m;
    while(low < high){
        m = low + (high - low) / 2;
        if (a[m] < key)
            low = m + 1;
        else
            high = m;
    }
    if (a[high] >= key)
        return high;
    return -1;
}

查找最大的比key值小于等于的数的下标， 若不存在， 返回负一。

1
2
3
4
5
6
7
8
9
10
11
12
13
int binary_search_6(int a[], int low, int high, int key){ // low high 为闭区间
    int m;
    while(low < high){
        m = low + (high - low + 1) / 2;
        if (a[m] <= key)
            low = m;
        else
            high = m - 1;
    }
    if (a[low] <= key)
        return low;
    return -1;
}

注

关于非递增的数组， 具体的二分我还不知， 暂且先翻转， 然后用非递减的数组来做。

1
恰似你一低头的温柔，娇弱水莲花不胜寒风的娇羞， 我的心为你悸动不休。  --mingfuyan