• 二分查找 三分查找与二分答案

    二分查找 三分查找与二分答案

    二分查找

    二分查找的前提

    目标函数具有单调性(单调递增或者递减)
    存在上下界(bounded)
    能够通过索引访问(index accessible)

    示例
    在单调递增数组里
    [10, 14, 19, 26, 27,31, 33, 35, 42, 44]
    查找: 33
    返回33所在的下标

    在这里插入图片描述

    在这里插入图片描述

    C++ / Java代码模板

    int left=0,right=n-1;
while (1eft <= right) {
	int mid = (1eft + right) / 2;
	if (array[mid] == target)
		// find the target!
		break or return mid;
	if (array[mid] < target)
		left=mid+1;
	else
		right = mid - 1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    Python代码模板

    left, right = 0，len(array) - 1
while left <= right:
	mid = (left + right) // 2
	if array[mid] == target:
		# find the target!
		break or return mid
	elif array[mid] < target:
		left=mid+1
	else:
		right=mid-1

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    实战

    704.二分查找
    https://leetcode.cn/problems/binary-search/

    class Solution {
public:
    int search(vector<int>& nums, int target) {

        int n=nums.size();
        int left=0;
        int right=n-1;

        int mid=(left+right)/2;

        while(left<=right){
            mid=(left+right)/2;
            if(nums[mid]==target)
            {
                return mid;
            }else if(nums[mid]>target)
            {
                right=mid-1;
            }else{
                left=mid+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

    lower_ bound

    在单调递增数组里
    [10, 14, 19, 25, 27,31,33, 35, 42, 44]
    查找第一个>=31的数(返回下标)
    不存在返回 array.length

    upper_ bound

    在单调递增数组里
    [10, 14, 19, 25, 27,31,33, 35, 42, 44]
    查找第一个> 26的数(返回下标)
    不存在返回array.length

    lower_ bound和upper_ bound的问题是:
    给定的target不一定在数组中存在
    array[mid]即使不等于target,也可能就是最后的答案,不能随便排除在外

    在这里插入图片描述

    解决方案

    根据个人喜好，掌握三种二分写法中的一种

    • (1.1)+(1.2): 最严谨的划分，一侧包含，一侧不包含，终止于left == right
    • (2): 双侧都不包含，用ans维护答案,终止于left > right
    • (3):双侧都包含,终止于left+ 1 == right, 最后再检查答案

    “90%的程序员都写不对二分”
    所以必须熟记这三种之一

    适用性更广的二分模板(1.1 -后继型)

    查找lower_ bound (第一个>= target的数) ,不存在返回n

    int 1eft = 0, right = n;
while (left < right) {
	int mid = (left + right) 》1;
	if (array[mid] >= target) // condition satisfied, should be included
		right = mid;
	else
		1eft=mid+1;
}
return right ;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    改为array[mid] > target 就是upper _bound

    适用性更广的二分模板(1.2 -前驱型)

    查找最后一个<= target的数，不存在返回-1

    int left=-1,right=n-1;
while (1eft < right) {
	int mid=(left+right+1)>>1;
	if (array[mid] <= target) // condition satisfied, should be included
		left = mid; 
	else
		right = mid - 1;
}
return right;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    适用性更广的二分模板(2)

    也可以这样写

    int left=0,right=n-1;
int ans = -1;
while (1eft <= right) {
	int mid = (left + right) / 2;
	if (array[mid] <= target) {
		// update ans using mid
		ans = max(ans, mid);
		left=mid+1;
	} else {
		right = mid - 1;
	}
}

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

    适用性更广的二分模板(3)

    还可以这样写

    int left=0,right=n-1;
while (left + 1 < right) {
	int mid = (1eft + right) 1 2;
	if (array[mid] <= target)
		left = mid;
	else
		right = mid;
}
//答案要么是left, 要么是right, 要么不存在
//此处检查left 和right, 返回一个合适的结果

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    实战

    153.寻找旋转排序数组中的最小值
    https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/

    class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size() - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if(nums[mid] <= nums[right]) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return nums[right];
    }
};

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

    154.寻找旋转排序数组中的最小值II
    https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array-ii/

    class Solution {
public:
    int findMin(vector<int>& nums) {
        int low = 0;
        int high = nums.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (nums[pivot] < nums[high]) {
                high = pivot;
            }
            else if (nums[pivot] > nums[high]) {
                low = pivot + 1;
            }
            else {
                high -= 1;
            }
        }
        return nums[low];
    }
};




    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    推荐使用1.1+1.2
    只要“条件"单调，二分就适用

    • 旋转排序数组中的最小值，序列本身并不单调
    • 但“≤结尾"这个条件,把序列分成两半,一半不满足(>结尾) , 一半满足(≤结尾)
      可以把“条件满足”看作1,不满足看作0,这就是一一个0/1分段函数,二分查找分界点

    写出正确的二分代码“三步走”:

    1. 写出二分的条件(一般是一个不等式，例如upper_bound: > val的数中最小的)
    2. 把条件放到if…)里，并确定满足条件时要小的(right = mid)还是要大的(left = mid)
    3. 另一半放到else里(left= mid+ 1或right=mid- 1)，如果是后者,求mid时补+1

    如果题目有无解的情况，. 上界增加1或下界减小1,用于表示无解。

    74.搜索二维矩阵
    https://leetcode.cn/problems/search-a-2d-matrix/

    class Solution {
public:
    bool searchMatrix(vector<vector<int>> matrix, int target) {
        auto row = upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector<int> &a) {
            return b < a[0];
        });
        if (row == matrix.begin()) {
            return false;
        }
        --row;
        return binary_search(row->begin(), row->end(), target);
    }
};


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

    69. x的平方根
    https://leetcode.cn/problems/sqrtx/

    class Solution {
public:
    int mySqrt(int x) {
        long left = 0, right = x;
        while(left < right) {
            long mid = (left + right + 1) / 2;
            if(mid <= x / mid) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return right;
    }
};

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

    34.在排序数组中查找元素的第一个和最后一个位置
    https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

    class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans;
        int left = 0, right = nums.size();
        while(left < right) {
            int mid = (left + right) / 2;
            if(nums[mid] >= target) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        ans.push_back(right);

        left = -1, right = nums.size() - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if(nums[mid] <= target) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        ans.push_back(right);

        if(ans[0] > ans[1]) return {-1, -1};
        return ans;
    }
};

    • 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
    class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return vector<int> {-1, -1};
        int left=leftRound(nums,target);
        int right=rightRound(nums,target)-1;
        if (left == nums.size() || nums[left] != target) {
            return vector<int>{-1, -1};
        }

        return vector<int> {left,right};

    }

    int leftRound(vector<int>& nums,int target)
    {
        int left=0;
        int right=nums.size();
        int mid;

        while(left<right)
        {
            mid=(left+right)/2;
            if(nums[mid]>=target)
            {
                right=mid;
            }else
            {
                left=mid+1;
            }
        }

        return left;
    }

    int rightRound(vector<int>& nums,int target)
    {
        int left=0;
        int right=nums.size();
        int mid;

        while(left<right)
        {
            mid=(left+right)/2;
            if(nums[mid]>target)
            {
                right=mid;  
            }else
            {
                left=mid+1;
            }
        }

        return left;
    }


    // 主函数
vector<int> searchRange1(vector<int>& nums, int target)
{
    if (nums.empty()) return vector<int> {-1, -1};
    int lower = lower_bound(nums, target);
    int upper = upper_bound(nums, target) - 1; // 这里需要减1位
    if (lower == nums.size() || nums[lower] != target)
    {
        return vector<int> {-1, -1};
    }
    return vector<int> {lower, upper};
}
// 辅函数
int lower_bound(vector<int> &nums, int target)
{
    int l = 0, r = nums.size(), mid;
    while (l < r)
    {
        mid = (l + r) / 2;
        if (nums[mid] >= target)
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return l;
}
// 辅函数
int upper_bound(vector<int> &nums, int target)
{
    int l = 0, r = nums.size(), mid;
    while (l < r)
    {
        mid = (l + r) / 2;
        if (nums[mid] > target)
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
        
    }
    return l;
}

    



};

    • 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
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112

    三分查找

    在这里插入图片描述

    三分法用于求单峰函数的极大值( 或单谷函数的极小值)
    三分法也可用于求函数的局部极大/极小值
    要求:函数是分段严格单调递增/递减的(不能出现一段平的情况)

    以求单峰函数f的极大值为例，可在定义域[l,r]上取任意两点lmid, rmid

    • 若f(lmid) <= f(rmid),则函数必然在Imid处单调递增，极值在[lmid, r]上
    • 若 f(mid) > f(rmid),则函数必然在rmid处单调递减，极值在[l, rmid]上

    lmid, rmid可取三等分点
    也可取lmid为二等分点, rmid为lmid稍加一点偏移量
    取黄金分割点最快*

    在这里插入图片描述

    实战

    162.寻找峰值
    https://leetcode.cn/problems/find-peak-element/

    class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while( left < right) {
            int lmid = (left + right)/2;
            int rmid = lmid + 1;
            if( nums[rmid] <= nums[lmid] ){
                right = rmid - 1;
            }else {
                left = lmid + 1;
            }
        }
        return right;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    374.猜数字大小
    https://leetcode.cn/problems/guess-number-higher-or-lower/

    class Solution {
public:
    int guessNumber(int n) {
        return (size_t)partition_point((bool*)1, (bool*)n, [] (const bool& i) {
            return guess(size_t(&i)) == 1;
        });
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    猜数游戏的规则如下:

    • 每轮游戏,我都会从1到n随机选择一个数。
    • 请你猜选出的是哪个数。
    • 如果你猜错了， 我会告诉你，你猜测的数比我选出的数是大了还是小了。

    二分答案最优性问题转化为判定问题的基本技巧

    二分答案

    对于一个最优化问题
    求解:求一个最优解(最大值/最小值)
    判定:给一个解，判断它是否合法(是否能够实现)

    “判定”通常要比“求解”简单很多.
    如果我们有了一个判定算法，那把解空间枚举+判定-遍，就得到解了

    当解空间具有单调性时，就可以用二分代替枚举,利用二分+判定的方法快速求出最优解，这种方
    法称为二分答案法

    例如:求解-猜数;判定一 大了还是小了;
    低效算法: 1到n挨个猜-遍;高效算法: 1 二分

    实战

    410.分割数组的最大值
    https://leetcode.cn/problems/split-array-largest-sum/

    class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        int left = 0, right = 0;
        for(int num : nums) {
            left = max(left, num);
            right += num;
        }
        while(left < right) {
            int mid = (left + right) / 2;
            if(validate(nums, m, mid)) {
                right = mid;
            }else {
                left = mid + 1;
            }
        }
        return right;
    }

private:
    bool validate(vector<int> & nums,int m, int size) {
        int box = 0;
        int count = 1;
        for(int num : nums) {
            if(box + num <= size) {
                box += num;
            }else {
                count++;
                box = num;
            }
        }
        return count <= m;
    }
};

    • 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

    给定一个非负整数数组nums和一一个整数m，你需要将这个数组分成m个非空的连续子数组。
    设计一个算法使得这m个子数组各自和的最大值最小。

    求解:最小化"m个子数组各自和的最大值”
    判定:给一个数值T，"m 个子数组各自和的最大值<= T”是否合法
    换一一种说法:“ 能否将nums分成m个连续子数组，每组的和<= T”

    为什么是"<=T" ?
    nums= [7,2,5,10,8], -共有四种方法将nums分割为2个子数组
    [7][2,5,10,8], sum=[7, 25], max = 25
    [7,2][5,10,8], sum=[9, 23], max =23
    [7,2,5][10,8], sum=[14, 18], max= 18
    [7,2,5,10][8], sum=[24, 8], max=24
    ”能否将nums分成m个连续子数组，每组的和=T”一 只有18, 23, 24, 25合法
    “能否将nums分成m个连续子数组,每组的和<= T”一17之 前不合法, 18之后合法

    “能否将nums分成m个连续子数组，每组的和<= T”
    这个解空间具有特殊的单调性 ---- 单调分段 0/1函数
    在这里插入图片描述

    直接求出18比较困难，但可以通过猜测一一个值T， 判断T是否合法(true or false)，从而得知答
    案是在T左侧还是右侧
    最高效的猜测方法当然就是二分

    通常用于最优化问题的求解

    • 尤其是在出现“最大值最小”“最小值最大” 这类字眼的题目上
    • “最大值最小”中的“最小”是一 个最优化目标，“最大” -般是一个限制条件(例如:限
      制划分出的子数组的和)

    对应的判定问题的条件通常是一个不等式
    ●不等式就反映了上述限制条件

    关于这个条件的合法情况具有特殊单调性

    此时就可以用二分答案把求解转化为判定的技巧

    二分答案的本质是建立一个单调分段0/1函数
    定义域为解空间(答案)值域为 0或1,
    在这个函数上二分查找分界点

    1482.制作m束花所需的最少天数
    https://leetcode.cn/problems/minimum-number-of-days-to-make-m-bouquets/

    class Solution {
public:
    int minDays(vector<int>& bloomDay, int m, int k) {
        int latestBloom = 0;
        for(int bloom : bloomDay) {
            latestBloom = max(latestBloom, bloom);
        }

        int left = 0, right = latestBloom + 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if(validateOnDay(bloomDay, m, k, mid)){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        if(right == latestBloom + 1) return -1;
        return right;
    }

private:
    bool validateOnDay(vector<int>& bloomDay, int m, int k, int now) {
        int bouquet = 0;
        int consecutive = 0;
        for(int bloom : bloomDay) {
            if(bloom <= now) {
                consecutive++;
                if(consecutive == k) {
                    bouquet++;
                    consecutive = 0;
                }
            }else{
                consecutive = 0;
            }
        }
        return bouquet >= m;
    }
};

    • 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

    1011.在D天内送达包裹的能力
    https://leetcode.cn/problems/capacity-to-ship-packages-within-d-days/

    class Solution {
public:
    int shipWithinDays(vector<int>& weights, int days) {
        // 确定二分查找左右边界
        int left = *max_element(weights.begin(), weights.end()), right = accumulate(weights.begin(), weights.end(), 0);
        while (left < right) {
            int mid = (left + right) / 2;
            // need 为需要运送的天数
            // cur 为当前这一天已经运送的包裹重量之和
            int need = 1, cur = 0;
            for (int weight: weights) {
                if (cur + weight > mid) {
                    ++need;
                    cur = 0;
                }
                cur += weight;
            }
            if (need <= days) {
                right = mid;
            }
            else {
                left = mid + 1;
            }
        }
        return left;
    }
};



    • 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

    911.在线选举
    https://leetcode.cn/problems/online-election/

    class TopVotedCandidate {
public:
    vector<int> tops;
    vector<int> times;

    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        unordered_map<int, int> voteCounts;
        voteCounts[-1] = -1;
        int top = -1;
        for (auto & p : persons) {
            voteCounts[p]++;
            if (voteCounts[p] >= voteCounts[top]) {
                top = p;
            }
            tops.emplace_back(top);
        }
        this->times = times;
    }
    
    int q(int t) {
        int pos = upper_bound(times.begin(), times.end(), t) - times.begin() - 1;
        return tops[pos];
    }
};



    • 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

    875.爱吃香蕉的珂珂
    https://leetcode.cn/problems/koko-eating-bananas/

    class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int low = 1;
        int high = 0;
        for (int pile : piles) {
            high = max(high, pile);
        }
        int k = high;
        while (low < high) {
            int speed = (high - low) / 2 + low;
            long time = getTime(piles, speed);
            if (time <= h) {
                k = speed;
                high = speed;
            } else {
                low = speed + 1;
            }
        }
        return k;
    }

    long getTime(const vector<int>& piles, int speed) {
        long time = 0;
        for (int pile : piles) {
            int curTime = (pile + speed - 1) / speed;
            time += curTime;
        }
        return time;
    }
};


    • 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

    推荐一个零声学院免费公开课程，个人觉得老师讲得不错，分享给大家：Linux，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK等技术内容，立即学习

  • 相关阅读:
    C语言-结构体（7）
    让你的Mac体验更便捷，快速启动工具Application Wizard为你助力！
    Graph Convolutional Module for Temporal Action Localization in Videos GCM论文阅读笔记
    微服务架构 Sentinel 的服务限流及熔断
    【二】kubernetes master单节点拓展为集群
    【华为云云耀云服务器L实例评测｜使用教学】一文带你快速入手华为云云耀云服务器L实例
    ES 中时间日期类型 “yyyy-MM-dd HHmmss” 的完全避坑指南
    2022爱分析·数字人厂商全景报告 | 厂商征集
    如何将wav转为mp3格式，wav中间mp3步骤
    统信系统CEF项目研发环境构建
  • 原文地址：https://blog.csdn.net/qq_46118239/article/details/126806182