二分查找总结

Posted on | In
  • 没有重复元素时，目标值若存在，则返回索引；若不存在，返回 -1
  • 存在重复元素时，目标值若存在，则返回最小索引；若不存在，返回 -1

模板 2 - lower_bound

  • 返回大于(含等于)目标值的最小索引（第一个大于、等于目标值的索引返回0）

​

模板 3 - upper_bound

  • 返回大于等于目标值的最大索引+1（第一个大于目标值的索引返回3）

​

注意点：

- 跳出时都有lo + 1 == hi统一返回lo + 1或hi

- lo = -1 and hi = nums.size()和 lo = 0 and hi = nums.size() - 1取中时一致
有时也可取一边开一边闭的区间，注意最后收缩时的情况即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/*为什么返回 `lo+1`，而不是 `hi`？（退出循环时有 lo + 1 == hi）
    模板开始时将 (lo, hi) 看做是一个开区间，通过不断二分，最终这个区间中只会含有一个值，即 (lo, hi]
    返回 lo+1 的含义是，结果就在 lo 的下一个；
    在迭代的过程中，hi 会从开区间变为闭区间，而 lo 始终是开区间，
    (lo,hi]第一个在hi,[lo,hi)lo是等于的最大,而我们要返回大于的第一个,则返回 lo+1 显得更加统一。
    当然，这跟迭代的写法是相关的，你也可以使最终的结果区间是 [lo, hi)nums[mid]<=v，
    这取决于个人习惯。
*/

int binary_search(vector<int> nums, int  n){
    if(nums.size() < 1) return -1;
    int lo = -1, hi = nums.size();
    while(lo + 1 < hi){
        int mid = lo + (hi - lo)/2;
        if(nums[mid] < n)
            lo = mid;
        else
            hi = mid;
    }
  	if(hi == nums.size()) return -1;//lo+1 = hi,防止return时访问越界
    return nums[lo+1] == n ? lo+1 : -1;
}

//满足条件<lo往右,else收缩（low,high]终值在闭区间右侧上6667(-1,0]
int lowwer_bound(vector<int> nums, int  n){
    if(nums.size() < 1) return -1;
    int lo = -1, hi = nums.size();
    while(lo + 1 < hi){
        int mid = lo + (hi - lo)/2;
        if(nums[mid] < n)
            lo = mid;
        else
            hi = mid;
    }
    return lo + 1;
}

//满足条件<=lo往右,=继续往右找到[low,high)6667[2,3)
int upper_bound(vector<int> nums, int  n){
    if(nums.size() < 1) return -1;
    int lo = -1, hi = nums.size();
    while(lo + 1 < hi){
        int mid = lo + (hi - lo)/2;
        if(nums[mid] <= n)
            lo = mid;
        else
            hi = mid;
    }
    return lo + 1;
}

int main(){
    vector<int> test{1,2,2,3,4,6,6,6,8,9};
    auto ret = blowwer_bound(test, 10);
  	//10,下标已经越界,但和下题不同,下题要求找不到返回的是-1
    cout << ret;
}

做几道题测试一下，先别看答案。

LeetCode练习：34. Find First and Last Position of Element in Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int lowwer_bound(vector<int> nums, int  n){
    if(nums.size() < 1) return -1;
    int lo = -1, hi = nums.size();
    while(lo + 1 < hi){
        int mid = lo + (hi - lo)/2;
        if(nums[mid] < n)
            lo = mid;
        else
            hi = mid;
    }
    if(hi == nums.size()) return -1;
    return nums[hi] == n ? hi : -1;
}
int upper_bound(vector<int> nums, int  n){
    if(nums.size() < 1) return -1;
    int lo = -1, hi = nums.size();
    while(lo + 1 < hi){
        int mid = lo + (hi - lo)/2;
        if(nums[mid] <= n)
            lo = mid;
        else
            hi = mid;
    }
    if(lo == -1) return -1;
    return nums[lo] == n ? lo : -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res;
    res.push_back(lowwer_bound(nums, target));
    res.push_back(upper_bound(nums, target));
    return res;
}

LeetCode154. 寻找旋转排序数组中的最小值 II（可重复)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
题目描述
    假设按照升序排序的数组在预先未知的某个点上进行了旋转。

    ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

    请找出其中最小的元素。

    无论数组中是否存在重复元素，都可以使用以下代码

思路：
    二分查找，具体看代码
*/

int findMin(vector<int>& nums) {
    if(nums.size() < 1) return 0;
    int lo = -1, hi = nums.size() - 1;//由于和nums[hi]比较左开右闭
    while(lo + 1 < hi){
        int mid = lo + (hi - lo)/2;
        if(nums[mid] < nums[hi])//hi往左缩小的过程
            hi = mid;     //退出时(lo,hi] lo即左排序数组,nums[mid]<nums[hi]右排序数组,让hi = mid后退出
        else if (nums[mid] > nums[hi])
            lo = mid;
        else 
            hi--; //防止重复情况
    }
    return nums[lo + 1];
}

LeetCode 33. 搜索旋转排序数组

虽然可能通过各种条件判断直接一次二分，但是很容易出错

保险的做法是通过两次二分

  • 先找出最小值的位置(见上题LeetCode 153、154)，

  • 然后确定 target 的区间，再用一次二分去找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int search(vector<int>& nums, int target) {
    if(nums.size() < 1) return -1;
    int lo = -1, hi = nums.size() - 1;

     //找到旋转数组分界点hi
    while(lo + 1 < hi){
        int mid = lo + (hi - lo)/2;
        if(nums[mid] < nums[hi])
            hi = mid;
        else
            lo = mid;
    }

    if(nums[hi] == target) return hi;//开区间把hi去除
    if(nums[hi] < target && nums[nums.size()-1] >= target)
    {
        lo = hi;
        hi = nums.size();//左开右开区间
    }
    else
        lo = -1;//在左排序数组中

    /*
    错误写法，不能用左排序数组最大值来确定是否在左,要判断是否在右
    if(nums[lo] >= target) lo = -1;
    else hi = nums.size();
    */

    while(lo + 1 < hi){
        int mid = lo + (hi - lo)/2;
        if(nums[mid] < target)
            lo = mid;
        else
            hi = mid;
    }
    if(hi == nums.size()) return -1;
    return nums[hi] == target ? hi : -1;
}

附上常见的写法，其实本质是一样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template<typename T>
int binarySearch(vector<T> &vec, T key){
    if(vec.size() < 0)
        return -1;
    int low = 0;
    int high = vec.size() - 1;
    int mid = 0;
    //low=high时不能跳出，此时需要进去进行vec[mid]==key判断
    while(low <= high){
        mid = low + (high - low)/2;
        if(vec[mid] == key)
            return mid;
        if(vec[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    //没找到返回-1
    return -1;
}

扩展：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
二分查找最优解的模板：
    在一定精度下，求满足条件 C 的最大/小解 x

注意点：
    - 初始化上下界：
        求最大值时，将下界 lo 初始化为一个特殊的可行解；上界初始化为一个不满足条件的解
        求最小值时，反之
    - 一般这种最优解问题会提供精度要求，需要在返回时处理
        - 最大值用“下取整” floor(ret * 1000) / 1000 ——三位精度，floor: 地板
        - 最小值用“上取整” ceil(ret * 1000) / 1000  ——三位精度，ceil:  天花板

*/

/*例 1：
求大于 目标值 v(>0) 的最小值，精确到 3 位小数
*/
double min_bigger(double v) {
    // 初始化上下界
    double lo = v - EPSILON, hi = INF;
    for (size_t i = 0; i < 100; i++) {          // 100 次循环已经能达到相当的精度
        double mid = lo + (hi - lo) / 2.0;
        if (mid <= v)
            lo = mid;
        else
            
            hi = mid;
    }
    // 因为 hi 在解空间中（hi 必大于 v），所以返回 hi
    return ceil(hi * 1000) / 1000; // 三位精度
}


/*例 2：POJ No.1064
    有 N 条绳子，长度分别为 Li。如果从它们中切割出 K 条长度相同的绳子，求这 K 条绳子的最大长度。答案保留 2 位小数。
*/
class Solution {
public:
    double max_length(vector<double> ls, int k) {
        double lo = 0, hi = INF;

        for (size_t i = 0; i < 100; i++) {
            double mid = lo + (hi - lo) / 2;

            if (C(ls, mid, k))
                lo = mid;
            else
                hi = mid;
        }
        // 因为 lo 在解空间中，所以返回 lo
        return floor(lo * 100) / 100;
    }
    
private:
    bool C(vector<double> ls, double mid, double k) {
        int n = 0;
        for (size_t i = 0; i < ls.size(); i++) {
            n += ls[i] / mid;
        }
        return n >= k; 
        // n >= k 说明还有加大的空间，所以当 C 返回 true 时，lo = mid
    }
};