【二分法】多种情况下的边界条件，区间选择汇总，小结

1 二分法

参考：
《算法通关之路》
labuladong的算法小抄

1.1 二分查找

• 二分查找又称折半搜索算法，狭义来讲，二分查找是一种在有序数组查找某一特定元素的搜索算法；广义来讲，将问题的规模缩小到原有的一半；

• 二分查找的细节问题很多注意！

• 术语

  • target：要查找的值；

  • index：当前位置；

  • l和r：左右指针；

  • mid：左右指针的中点，用来确定我们应该向左查找还是向右查找的索引；

• 解空间

• 解空间：指题目所有可能的解构成的集合；可大不可小

• 目标：在某个具体情况下判断其具体是哪一个，如果线性枚举所有的可能，枚举部分时间复杂度就为O(n);

• 实数二分

  • 少部分题目的解空间包括小数，会涉及精度问题，例如求一个数x的平方根，答案误差在10-6次方都认为正确，解空间大小定义为[1,x],包括所有区间的实数，不仅仅整数而已，称为实数二分；这个时候有两种变化：

    • 1）更新答案的步长：例如之前的更新是 l = mid + 1，现在可能就不行了，因此这样可能会错过正确解，比如正确解恰好就在区间 [mid,mid+1] 内的某一个小数。
    • 2）判断条件时候考虑误差：由于精度问题，判断结束条件变成与答案的误差在某一个范围内。

• 序列有序

• 序列有序中的序列：不一定是数组、链表、有可能是其他数据结构；

• 有些题目没有有序关键字，比如题目给了数组nums,并且没有限定nums有序，但限定了nums为非负，如果给nums进行前缀和或前缀或（位运算或），可以得到一个有序序列。

• 一个中心

  • 折半才是二分法的灵魂

1.2 查找一个数

• 1、区间选取问题

  • 由于定义的搜索区间为 [left, right]，因此当 left <= right 的时候，搜索区间都不为空，此时我们都需要继续搜索。 也就是说终止搜索条件应该为 left <= right。

    举个例子容易明白一点。 比如对于区间 [4,4]，其包含了一个元素 4，因此搜索区间不为空，需要继续搜索（试想 4 恰好是我们要找的 target，如果不继续搜索， 会错过正确答案）。而当搜索区间为 [left, right) 的时候，同样对于 [4,4)，这个时候搜索区间却是空的，因为这样的一个区间不存在任何数字·。

1.2.1 左闭右闭

• 代码实现

int binarySearch(vector<int>& nums,int target){
    //采用左闭右闭区间
    int left = 0;
    int right = nums.size()-1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] > tagert)right = mid - 1;
        else if(nums[mid] < target)left = mid + 1;
        else return mid;
    }
    //左闭右闭区间结束，left=right+1 //此时，没有target，返回-1
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.2.2 左闭右开

• 代码实现

int binarySearch(vector<int>& nums,int target){
    //采用左闭右开区间
    int left = 0;
    int right = num.size();
    while(left < right){//此处不同
        int mid = left + (right - left) / 2;
        if(nums[mid] < target)left = mid + 1;
        else if(nums[mid > target])rigth = mid;//此处不同
        else return mid;
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12

1.3 寻找最左满足条件的边界

• 说明
  • 应该插入的位置，使得插入之后列表仍然有序；
  • 另外如果有多个满足条件的值，我们返回最左侧的。 比如一个数组 nums: [1,2,2,2,3,4]，target 是 2，我们应该插入的位置是 1
• 寻找最左，用右边逼近最左边

1.3.1 左闭右闭

• 代码实现

int leftBound(vector<int>& nums,int target){
    //采用左闭右闭区间 --- 精简 --- 合并相等情况
    int left = 0;
    int right = nums.size()-1;
    while(left <= right){
        int mid = left + ((right - left) >> 1);
        if(nums[mid] >= target)right = mid - 1;
        else left = mid + 1;
    }
    //结束时，left == right + 1，[right,right+1(left)],需要检查是否越界
    //left<=right,最大就是right + 1 = nums.size()
    if(left == num.size() || nums[left] != target)return -1;
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.3.2 左闭右开

• 代码实现

int leftBound(vector<int>& nums,int target){
    //采用左闭右开区间 --- 精简 --- 合并相等情况
    int left = 0;
    int right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] >= target)right = mid;
        else left = mid + 1;
    }
    //结束时，[left,right],left == right
    //target很大，left一直右移
    if(left == nums.size() || nums[left] != target)return -1;
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.4 寻找最右满足条件的边界

1.4.1 左闭右闭

• 代码实现

int rightBound(vector<int>& nums,int target){
    //采用左闭右闭区间
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        //最右，左边逼近
        if(nums[mid] <= target)left = mid + 1;
        else right = mid - 1;
    }
    //结束时，[right, left],left == right+1;
    //1、分析返回值，return left - 1 / right;
    //2、分析越界情况，left->[0,nums.size()],left -1 ->[-1,nums.size()-1]
    if(left - 1 < 0 || nums[left - 1] != target)return -1;
    return left - 1;//return right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.4.2 左闭右开

• 代码实现

int rightBound(vector<int>& nums,int target){
    //采用左闭右开区间
    int left = 0;
    int right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] <= target)left = mid + 1;
        else right = mid;
    }
    if(left - 1 < 0 || nums[left - 1] != target)return -1;
    //结束时，[left,right]left == right,
    return left - 1;//return right - 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 为什么返回left/right-1？

• 最后的判断处理

• 小结：

• 1、判断返回值，通过nums[mid] == target情况判断，分析left/right与mid的关系；
• 2、判断越界，分析left，right的取值范围；

1.5 寻找最左插入位置

• 找不到不应该返回-1，而是返回应该插入的位置；

1.5.1 左闭右闭

• 代码实现

void leftInsert(vector<int>& nums,int target){
    //采用左闭右闭区间,右边逼近左边
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] >= target)right = mid - 1;
        else left = mid + 1;
	}
    //结束：[right,left(right + 1)],left = right + 1
    //mid = right + 1 = left
    //范围：left->[0,nums.size()],不需要进行区间，相等检查
    return left;//return right + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.5.2 左闭右开

• 代码实现

void leftInsert(vector<int>& nums,int target){
    //采用左闭右开区间，右边逼近左边
    int left = 0;
    int right = nums.size();
    while(left < right){
        int mid = left + (right -left) / 2;
        if(nums[mid] >= target)right = mid;
        else left = mid + 1;
    }
    //结束，right = left,[left,right],
    //mid = right;left->[0,nums.size()]
    return left;//return right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.6 寻找最右插入位置

1.6.1 左闭右闭区间

• 代码实现

void rightInsert(vector<int>& nums,int target){
    //采用左闭右闭，左边逼近右边
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(nums[mid] <= target)left = mid + 1;
        else right = mid - 1;
    }
    //结束，[right,left(right + 1)],left = right + 1;
    //mid = left - 1 = right;left->[0,nums.size()],
    //left-1 -> [-1,nums.size()-1],注意，是寻找右边插入位置，因此+1    
    return left;//return right + 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

1.6.2 左闭右开区间

• 代码实现

void rightInsert(vector<int>& nums,int target){
    //采用左闭右开区间,左边逼近右边
    int left = 0;
    int right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] <= target)left = mid + 1;
        else right = mid;
    }
    //结束，[left,right],left == right, mid = left - 1;
    //left->[0,nums.size()]
    return left;//return right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13