AI 助理
备案控制台
开发者社区 云原生 文章 正文

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

2024-01-10 65
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 二分查找 三分查找与二分答案


二分查找

二分查找的前提

目标函数具有单调性(单调递增或者递减)

存在上下界(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;
}

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

实战

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;
    }
};

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 ;

改为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;

适用性更广的二分模板(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;
  }
}

适用性更广的二分模板(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, 返回一个合适的结果

实战

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];
    }
};

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.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);
    }
};

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;
    }
};

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;
    }
};
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;
}
};

三分查找

三分法用于求单峰函数的极大值( 或单谷函数的极小值)

三分法也可用于求函数的局部极大/极小值

要求:函数是分段严格单调递增/递减的(不能出现一段平的情况)

以求单峰函数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;
    }
};

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到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;
    }
};

给定一个非负整数数组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;
    }
};

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;
    }
};

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];
    }
};

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;
    }
};

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

文章标签：
算法
容器
NoSQL
网络协议
Kubernetes
我也要当昏君
目录
相关文章
aliyun1792367740-35101
|
1月前
|
算法 C++
你真的懂二分吗？
你真的懂二分吗？
aliyun1792367740-35101
37 0
追逐时光者
|
1月前
|
算法 C# 索引
C#二分查找算法
C#二分查找算法
追逐时光者
16 1
bbbbyh
|
1月前
对二分的理解
对二分的理解
bbbbyh
31 2
陈佳烨
|
5月前
|
算法 搜索推荐 Java
二分查找算法详解及实现
二分查找算法详解及实现
陈佳烨
82 2
筱姌
|
6月前
|
算法 大数据
二分查找和二分答案
二分查找和二分答案
筱姌
57 1
给我杯冰美式
|
6月前
|
算法 索引
二分查找与二分答案
二分查找与二分答案
给我杯冰美式
35 0
aliyun9861394983-11302
|
6月前
|
算法 测试技术 API
深入理解二分查找算法(一)
深入理解二分查找算法(一)
aliyun9861394983-11302
141 0
闻缺陷则喜何志丹
|
6月前
|
算法 测试技术 C#
【二分查找】【双指针】LeetCode:2565最少得分子序列
【二分查找】【双指针】LeetCode:2565最少得分子序列
闻缺陷则喜何志丹
63 0
闻缺陷则喜何志丹
|
6月前
|
算法 测试技术 C#
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
[二分查找]LeetCode2040:两个有序数组的第 K 小乘积
闻缺陷则喜何志丹
50 0
猿长大人
|
6月前
|
存储 算法 C#
C# | 二分查找算法的实现
二分查找法一种在**有序数组**中查找目标值的算法。划重点——“**有序**”，与需要遍历整个数组的查询算法不同，二分查找法通过将数组分成两部分来快速定位目标值所在的位置。 它的主要好处在于它的效率很高。因为它能够通过每次排除一半的元素来快速缩小搜索范围，因此在大型数据集上使用二分查找法可以显著提高查找速度。
猿长大人
58 0