二分法的总结

二分法的主要用途

二分法主要是通过左右逼近的方式，向目标值靠拢，并且取得对数复杂度的算法。

二分法的分类

查找和目标值相等的元素

给定有序数组nums，寻找元素target

写法一

1
2
3
4
5
6
7
8
9
10
11
12
13

# n: nums数组的大小
# left: 左界限，初始化为0
# right: 右界限，初始化为n - 1
# target: 要寻找的值
while left <= right: # 说明要找的值当前在[left, right]
    mid = int(left + (right - left) / 2)
    if nums[mid] == target:
        return mid
    elif nums[mid] < target: # 说明要找的target在[mid + 1, right]
        left = mid + 1
    else: # nums[mid] > target，说明要找的target在[left, mid - 1]
        right = mid - 1
return -1 # 表示没找到

写法二

1
2
3
4
5
6
7
8
9
10
11
12
13

# n: nums数组的大小
# left: 左界限，初始化为0
# right: 右界限，初始化为n
# target: 要寻找的值
while left < right: # 说明要找的值当前在[left, right)
    mid = int(left + (right - left) / 2)
    if nums[mid] == target:
        return mid
    elif nums[mid] < target: # 说明要找的target在[mid + 1, right)
        left = mid + 1
    else: # nums[mid] > target，说明要找的target在[left, mid)
        right = mid
return -1 # 表示没找到

查找第一个不小于目标值的数(可变形为查找最后一个小于目标值的数)

这种情况就是对第一种情况的改进，主要是取消判断nums[mid] == target

1
2
3
4
5
6
7
8
9
10
11

int find(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) { // 说明要找的值在[left, right]里，等于n表面不存在这样的值
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1; // 说明要找的值在[mid + 1, right]中
        else right = mid; // 说明要找的值在[left, mid]中
    }
    return right; 
  	// 这里right对应的是第一个不小于目标值的数的下标
    // 如果要求解最后一个小于目标值的数，则返回right - 1
}

C++的STL中有两个函数，upper_bound和lower_bound：

在从小到大排列的数组nums中：
lower_bound(nums.begin(), nums.end(), target)
从nums数组的begin位置到end - 1位置二分查找第一个大于或等于target的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标；
upper_bound(nums.begin(), nums.end(), target)
从nums数组的begin位置到end - 1位置二分查找第一个大于target的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标；

在从大到小排列的数组nums中：
lower_bound(nums.begin(), nums.end(), target, greater())
从nums数组的begin位置到end - 1位置二分查找第一个小于或等于target的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去)始地址begin,得到找到数字在数组中的下标；
upper_bound(nums.begin(), nums.end(), target, greater())
从nums数组的begin位置到end - 1位置二分查找第一个小于target的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标；

查找第一个大于目标值的数(可变形为查找最后一个不大于目标值的数）

类似上一种情况，只不过对于nums[mid] == target的情况，需要找的结果在[mid + 1, right]中

1
2
3
4
5
6
7
8
9
10
11

int find(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) { // 说明要找的值在[left, right]里，等于n表面不存在这样的值
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) left = mid + 1; // 说明要找的值在[mid + 1, right]中
        else right = mid; // 说明要找的值在[left, mid]中
    }
    return right; 
  	// 这里right对应的是第一个大于目标值的数的下标
    // 如果要求解最后一个不大于目标值的数，则返回right - 1
}

mid对应的值由某个函数计算得出

即在第一种情况的基础上，在比较大小的地方使用了子函数去计算大小关系

1
2
3
4
5
6
7
8
9
10

int find(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (EQUAL(nums[mid], target)) return mid;
        else if (SMALLER(nums[mid], target)) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

target值不固定

target的值可能随mid变化，比如需要搜索局部峰值的时候，需要比较的是mid和两边的值，这个时候target就会根据mid所在位置的不同而产生变化。

总结

二分法主要的思想就是对在某种程度上有序的数组上寻找特定值或者特定范围的值，通过大小关系来判断应该选择左半段还是右半段继续进行迭代。注意要确定这里left或者right的取值的时候，需要通过判断具体值的范围，特别注意right值的初始值，为n的时候表示左闭右开，为n - 1的时候表示左闭右闭。

参考

https://www.cnblogs.com/grandyang/p/6854825.html