当前位置： 首页 > article >正文

【二分汇总】

article 2024/11/13 0:49:47

下面是三个模板，第一个是最容易理解的，第二三个需要背一下，基本满足所有二分题目

// 二分，查target的位置，最容易理解的
int bsearch_0(int[] nums, int l, int r)
{
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (nums[mid] == target) {
            // 找到
        } else if (num[mid] > target) {
            r = mid - 1;
        } else if (num[mid] < target) {
            l = mid + 1;
        }
    }
}
// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用：
// 一般用来找最左边的一个！因为当前mid如果符合条件，左边可能有或者没有，所以当前的mid不能丢掉
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;    // check()判断mid是否满足性质
        else l = mid + 1;
    }
    return l;
}
// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
//一般用来找最右边的一个！
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

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

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先找他的分界点，选择的是找最大的那个值，比如4,5,6,7,0,1,2。要找到的是7，就是4,5,6,7中最右边的那个数。板子：

// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用：
//一般用来找最右边的一个！
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

用nums[0]做基准。因为分界点之后的数字不可能比nums[0]大。

//找分界点
int l = 0, r = nums.size() - 1;
while(l < r){
    int mid = l + r + 1 >> 1;
    if(nums[mid] >= nums[0]) l = mid;
    else r = mid - 1;
}

找到之后只需要判断target在哪个区间，然后进行一次普通的二分就可以了。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        //找分界点,最大的那个数,找最右，板子2
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }

        //判断在哪个区间
        if(target >= nums[0]){
            l = 0;
        } else{
            l = r + 1, r = nums.size() - 1;
        }

        //普通二分
        while (l <= r){
            int mid = l + r >> 1;
            if(nums[mid] == target) return mid;
            else if(nums[mid] > target) r = mid - 1;
            else l = mid + 1;
        }

        return -1;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if(nums.empty()) return {-1, -1};
        //找最左，板子1
        int l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        if(nums[l] != target) return {-1, -1};
        res.push_back(l);
        //找最右，板子2
        l = 0, r = nums.size() - 1;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        res.push_back(l);
        return res;
    }
};

81. 搜索旋转排序数组 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

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

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

跟上个题类似，但是会有重复，比如2,2,2,0,2,2或者[1,3,1,1,1]。

题目板子大致跟上一个类似，就是找分界点，最大的数，用板子2。

至于怎么去除重复。。。

//去除开头和结尾的重复，压缩l
int l = 0, r = nums.size() - 1;
while(l != r && nums[l] == nums[r]){
    if(nums[l] == target) return true;
    else l++;
}
//记录基准点
int flag = l;

剩下的就跟I一样了

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.empty()) return false;
        //去除开头和结尾的重复，压缩l
        int l = 0, r = nums.size() - 1;
        while(l != r && nums[l] == nums[r]){
            if(nums[l] == target) return true;
            else l++;
        }
        //记录基准点
        int flag = l;
        //找分界点,板子2
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] >= nums[flag]) l = mid;
            else r = mid - 1;
        }

        if(target >= nums[flag]){
            l = flag;
        }else{
            l = r + 1, r = nums.size() - 1;
        }

        while (l <= r){
            int mid = l + r >> 1;
            if(nums[mid] == target) return true;
            else if(nums[mid] > target) r = mid - 1;
            else l = mid + 1;
        }

        return false;
    }
};

153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

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

请找出其中最小的元素。

你可以假设数组中不存在重复元素。

示例 1:

输入: [3,4,5,1,2]
输出: 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

那这个就直接用板子就好了，板子2，找到最大值之后，要么他是最后一个数，要么下一个就是最小值。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        //板子2,找最右边
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        if(r == nums.size() - 1){
            return nums[0];     
        }else{
            return nums[r + 1];
        }
    }
};

或者直接用板子1，找最小的数，就是找某一区间的最左边。这个时候就不能跟nums[0]比较了，要跟nums[nums.size() - 1]去比较。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        //板子1，找最左边的值
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] <= nums[nums.size() - 1]) r = mid;
            else l = mid + 1;
        } 
        return nums[l];
    }
};

154. 寻找旋转排序数组中的最小值 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

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

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]
输出: 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

熟悉套路之后这就不是一道难题了，要么做的出来，要么GG，既然有重复，那么就按之前的方式，把l压缩，再用板子1，找最小的元素（该区间中最左边的元素）。

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

162. 寻找峰值

峰值元素是指其值大于左右相邻值的元素。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[n] = -∞。

示例 1:

输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

找下规律就行了，看当前的mid和左右两边的关系，如果是峰值，就直接返回，不然就再迭代一下。

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size() == 1){
            return 0;
        } else if(nums.size() == 2){
            if(nums[0] < nums[1])
                return 1;
            else
                return 0;
        }
        nums.insert(nums.begin(), INT_MIN);
        nums.push_back(INT_MIN);
        int res = -1;
        int left = 0, right = nums.size() - 1;
        while (left < right){
            int mid = left + right + 1 >> 1;
            int mid_num = nums[mid];
            int mid_left_num = nums[mid - 1];
            int mid_right_num = nums[mid + 1];
            if(mid_num > mid_left_num && mid_num > mid_right_num){
                res = mid;
                break;
            } else if(mid_num > mid_left_num && mid_num < mid_right_num){
                left = mid;
            } else{
                right = mid;
            }
        }
        return res - 1;
    }
};

274. H 指数

给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。

h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数 不超过 h 次。）

例如：某人的 h 指数是 20，这表示他已发表的论文中，每篇被引用了至少 20 次的论文总共有 20 篇

示例：

输入：citations = [3,0,6,1,5]
输出：3
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/h-index
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题要关注的是i和citations[i]的关系，除去题目给的例子，再比如[5,4,1,0]的答案是2，所以答案不一定在数组中。我们必须要把数组按降序排序，然后搜索h，用二分法，找最右边的那个满足citations[mid] >= (mid + 1)的位置。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        if(citations.empty()) return 0;
        sort(citations.begin(), citations.end());
        reverse(citations.begin(), citations.end());
        int l = 0, r = citations.size() - 1;
        //板子2
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(citations[mid] >= (mid + 1)) l = mid;
            else r = mid - 1;
        }
        //判断一下是否合格
        if((r + 1) <= citations[r]) return r + 1;
        return 0;
    }
};

275. H 指数 II

给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照 升序排列 。编写一个方法，计算出研究者的 h 指数。

h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/h-index-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题已经升序排列，所以刚好更上面相反，所以我们倒过来用板子1，找最左边的那一个。

class Solution {
public:
    int hIndex(vector<int>& citations) {
        if(citations.empty()) return 0;
        int l = 0, r = citations.size() - 1;
        //板子1
        while(l < r){
            int mid = l + r >> 1;
            if(citations[mid] >= (citations.size() - mid)) r = mid;
            else l = mid + 1;
        }
        if((citations.size() - r) <= citations[r]) return citations.size() - r;
        return 0;
    }
};

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-bad-version
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题比较简单但是有一个小坑，测试用例会有超过max_int的数据，l + r >> 1的方式会不给过，就要换成l + (r - l) / 2。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1, r = n;
        //板子1 
        while(l < r){
            int mid = l + (r - l) / 2;
            if(isBadVersion(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};

分巧克力（蓝桥杯）

问题描述

儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
　　小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。

为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：

 　　1. 形状是正方形，边长是整数
      2. 大小相同

当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？

输入格式

第一行包含两个整数N和K。(1 <= N, K <= 100000)
　　以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
　　输入保证每位小朋友至少能获得一块1x1的巧克力。

输出格式

输出切出的正方形巧克力最大可能的边长。

样例输入

2 10
6 5
5 6

样例输出

2

起码能分出k块，比如[1,2,3,4,5,6,7]其中，[1,2,3]能分出k块，所以答案是3。就是找满足条件的最大值，即最右边的数，模板2。

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

int main(){
	int n, k;
	cin >> n >> k;
	vector<pair<int, int> > nums;
	for(int i = 0; i < n; i++){
		int hi, wi;
		cin >> hi >> wi;
		nums.push_back(make_pair(hi, wi));
	}
	
	int l = 1, r = 100000;
	while(l < r){
		int mid = l + r + 1 >> 1;
		int tmp = 0;
		for(int i = 0; i < n; i++){
			tmp += (nums[i].first / mid) * (nums[i].second / mid); 
		}
		if(tmp >= k){
			l = mid;
		}else{
			r = mid - 1;
		}
	}
	cout << l;
}

远亲不如近邻

牛牛最近搬到了一座新的城镇，这个城镇可以看成是一个一维的坐标系。城镇上有n个居民，第i个居民的位置为ai。现在牛牛有m个搬家方案，在第i个方案中他会搬到位置xi。

俗话说的好，远亲不如近邻。现在牛牛想知道，对于每个搬家方案，搬家后与最近的居民的距离为多少。

输入

3,2,[2,4,7],[5,8]

返回值

[1,1]

说明

第一个方案搬到位置5，与5最近的居民在位置4，距离为1.
第二个方案搬到位置8，与8最近的居民在位置7，距离为1
  • 两边的：每个方案先跟两边的比较，这样就不用进入二分。
  • 中间的：二分找第一个比他大的位置l，l-1就是第一个比他小的，比较与这两个位置的距离
class Solution {
public:
    /**
     * 远亲不如近邻
     * @param n int整型 居民个数
     * @param m int整型 方案个数
     * @param a int整型vector 居民的位置
     * @param x int整型vector 方案对应的位置
     * @return int整型vector
     */
    vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
        // write code here
        vector<int> res;
        if(a.empty() || x.empty()){
            return res;
        }
        sort(a.begin(), a.end());
        
        int len = x.size();
        for(int i = 0; i < len; i++){
            if(x[i] < a[0]){
                res.push_back(a[0] - x[i]);
            }else if(x[i] > a[a.size() - 1]){
                res.push_back(x[i] - a[a.size() - 1]);
            }else{
                //找第一个比他大的
                int l = 0, r = a.size() - 1;
                while(l < r){
                    int mid = l + r >> 1;
                    if(a[mid] > x[i]) r = mid;
                    else l = mid + 1;
                }
                res.push_back(min(a[r] - x[i], x[i] - a[r - 1]));
            }
        }
        return res;
    }
};

http://www.kler.cn/a/9971.html

相关文章：

  • 大数据新视界 -- 大数据大厂之 Impala 性能优化：优化数据加载的实战技巧（下）（16/30）
  • 万字长文解读深度学习——卷积神经网络CNN
  • 鸿蒙next打包流程
  • 自监督学习：机器学习的未来新方向
  • 树莓派安装FreeSWITCH
  • uniapp中使用全局样式文件引入的三种方式
  • 全国青少年信息素养大赛2023年python·选做题模拟二卷
  • 「计算机控制系统」2. 采样与数据保持
  • houjie-cpp面向对象
  • 刷题day54：柱形图中最大矩形
  • Java多线程基础面试总结（一）
  • 【数据挖掘与商务智能决策】第十一章 AdaBoost与GBDT模型
  • 数字孪生智慧应急怎么实现?
  • 运行时内存数据区之虚拟机栈——操作数栈
  • 你真正了解低代码么？(国内低代码平台状况分析)
  • 国家出手管人工智能AI了
  • Python数据分析案例24——基于深度学习的锂电池寿命预测
  • Difference between HTTP1.0 and HTTP1.1
  • Spring 之依赖注入底层原理
  • like字符通配符%_、查询空值、去重、and、or、MySQL数据库 - 单表查询（二）（头歌实践教学平台）
  • 【数据结构】栈各个接口的实现
  • 详解AUTOSAR：Green Hills Software（GHS）集成DaVinci Configurator生成的代码（RH850）（环境配置篇—1）
  • springboot+vue学生选课管理系统
  • 循环依赖详解及解决方案
  • 闭包和继承
  • 程序员为了女朋you进了华为，同学去了阿里，2年后对比收入懵了