二分法

二分图的判定 记无向图 \(G = (V, E)\)，若存在点集 \(A,B\) 满足： \(A \cup B = V\) \(A \cap B = \varnothing\) \(\forall e = (u,v) \in E\), 满足 \(u,v\) 不同时在 \(A\) 或 \(B\) 中。 ......

二分图 前情提要：今日速查打二分图最大匹配，发现自己的匈牙利算法《学的非常好》，于是一怒之下写了这篇笔记 1.什么是二分图？ 若一张无向图\(G\)的\(N\)个节点可分成\(A、B\)两个不相交的非空集合，并且同一集合内的点之间没有边相连，那称该图为二分图 性质：二分图中不存在奇环（一个点想回到自 ......

二分答案的写法有很多模板，但使用的情况各不相同 前两种模板：都是 while(l < r)，但是会有区别的，区别在代码注释中有体现。 后两种模板：都是 while(l <= r)， 也是在返回上有区别。 这是最大值最小 int main() { int l; int r; while(l < r) ......

// // main.c // BinarySearch // // Created by steve xiaohu zhao on 2023/10/16. // #include <stdio.h> // 二分法查找指定元素在数组中出现的索引位置 int BinarySearch(int *arr ......

二分 二分是一种基于一个具有非严格单调性的序列上进行搜索的算法，其复杂度为 \(O(logn)\)，在单调性的前提下，效率碾压遍历不知道多少倍。 原理 我们以下图中长度 \(n=10\) 的非严格单调递增序列 \(P\) 为例 假设此时我们询问一个数 \(x\)，我们需要在序列中找到一个数 \(y\ ......

本文是写给作者自己看的 概念 指一张无向图G中，N个节点可以划分为两个集合A,B 集合A和B内部没有连边，A和B可以有连边（可以有空集） Q：为什么不用三分图： A：很简单，三分图分类更多，更麻烦。没有顺序关系有三种情况，有顺序关系则是六种（就像线段树不用三叉） 一些叫法 A集合内的点：左部点 B集 ......

描述 有n个数字，a1，a2，...，an。 给出左右两个端点l和r，你的任务找到有多少个数字在l和r之间（包括端点）。 输入 输入的第一行有一个n（1≤n≤105）。 第二行包含n个数字，a1，a2，...，an（1≤a≤109）； 第三行有一个k（1≤k≤105）。 接下来k行，每行有两个数字l ......

题目描述：龙龙得知2020年中国将有2000万至4000万男人娶不到老婆后。他打算好好调查一下是不是人们的感情出现问题。他对n个人进行调查，得到m条信息，每条信息表示为某两人曾经是情侣。由于他不知道这些人的性别，请你帮他判断一下，有没有同性是情侣的情况？ 对于100%的数据，n的范围[2,10000 ......

整数二分边界 bool check(int x) {/* ... */} // 检查x是否满足某种性质 // 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用： int bsearch_1(int l, int r) { while (l < r) { int mid = l ......

对数器 非常重要的自我验证代码正确性的方法 在面试时或机试时写算法题，没有测试用例或者测试用例太少，导致巨大的数据量无法进行测试时。需要自己写测试用例数据时可以使用对数器。 ......

一、算法简介 浮点数二分相比与整数二分就要简单很多了，但是还是要注意范围的问题。 以下给出一个小例子，求 \(x\) 的平方根，\(x\) 的范围在 \([0, 10000]\) 内： #include <iostream> #include <cmath> using namespace std; ......

描述 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 示例1 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nu ......

二分图的概念 第1幕·第1场·二分图的概念 定义 若有一个无向图，其所有节点可以被分为两个不相交的非空集合，且同一集合中的点之间没有边，那么称该图为二分图。 形式化地，对于一张图\(G = \{V, E\}\)，若有集合\(A,B\)满足： \((A,B\subseteq V)\and (A\cap ......

使用洛谷P1873举例 看出这个题目考的是二分答案 找出题目横纵坐标，横坐标是我们要输出的东西(也是L和R)，纵坐标是输入的m，理解题目，观察横纵坐标的递增递减关系 这个题目里面输入的m是所得到的木材，横坐标是锯片的高度，锯片越高得到的木材越少，所以是递减关系 开始写二分模板，写check函数，与c ......

Day1 二分查找两种写法和快慢指针 //左闭右闭的情况，也是我最喜欢的一种写法，可能是因为比较对称 一个mid+1 一个mid—1 直接写就行，要注意左闭右闭和左闭右开的区别class Solution {public: int search(vector<int>& nums, int targ ......

一、算法简介 二分法，即二分搜索法，是通过不断缩小解可能存在的范围，从而求得问题最优解的方法。 例如，如果一个序列是有序的，那么可以通过二分的方法快速找到所需要查找的元素，相比线性搜索要快不少。 此外二分法还能高效的解决一些单调性判定的问题。 二分的关键不在于单调性，或者说二分的本质并不是单调性。 ......

704. 二分查找 链接：https://leetcode.cn/problems/binary-search/description/ 思路：关键是定义清楚区间边界，想清楚middle在计算中是否可能取到左边界or右边界。若采用闭区间，则middle可能等于左/右 边界值。 27. 移除元素 链接 ......

Leetcode 704 二分查找 题目链接：704 二分查找 关键点思路: 1、是否要进入到 while 部分的代码是 left <= right 还是 left < right, 看 [left, right] 是否是合法区间. 例如 [1, 1] 是合法区间，取<=; [1, 1) 非合法区间 ......

搜索算法：1.线性搜索：循环遍历，判断是否等于目标值2.二分法：（需要有序）先定一个起点和终点left,right，当left<right时，取中间值mid，如果目标值小于mid，则right=mid-1,反之亦然 # 线性搜索 def action1(arr, target): for i in ......

704.二分查找 题目链接：704.二分查找 视频教程 文章教程 思路 利用 middle 去寻找 target 前提条件： 这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，二分查找法返回的元素下标可能就不唯一，这些都是二分法的前提，以后看到题目描述后可以先想一想 ......

不同于有序数组的简单二分查找，789. 数的范围在更新区间时包含mid，需要考虑边界问题。 1. 题目描述 给定一个按照升序排列的长度为n的整数数组a，返回一个元素k的起始位置和终止位置（位置从0开始计数）。 2. 解题思想 解题思想比较直接，就是分别找到第一个不小于k的元素和最后一个不大于k的元素 ......

二分法原理： 使用二分法一定要是先排序好的数组，如果没有排序好，比较只有可能怎么找都找不到 数组： 10(下标0) 11 12 13 14 15 16 17 18 19 20(下标10) 通过二分法查找，例如需要找出19这个元素的下标： (0 + 10) / 2 --> 中间元素的下标： 5 拿着中 ......

就是跑匈牙利算法就行了，难点完全在于建图。 模板水题 Link #include <bits/stdc++.h> const int N=510; int n,m,e; int G[N][N],match[N]; std::bitset<N> vis; namespace BlackWhiteGra ......

动态规划——带权二分优化DP 学习笔记 引入 带权二分其实并不一定用于优化 DP，也可能用于优化贪心等最优化的算法。 带权二分也叫 WQS 二分，最初由王钦石在他的 2012 年国家集训队论文中提出。 定义 使用情况 要解决一个最优化问题（求最大 / 最小值） 有一个限制，一般是某个参数要求一定恰好 ......

#include<bits/stdc++.h> using namespace std; bool judge(int x) { } int main() { int l,r; //000000000111111111 while(l < r) { int mid = l+r>>1; if(judg ......

CF1139E 翻译中有一句话：校长将会从每个社团中各选出一个人。 就是一些人被分为一组，从每组中选一些人出来。 这就很容易想到通过二分图的匹配。 \(\operatorname{mex}\) 运算有一个显而易见的贪心：枚举每个值能否被匹配，第一个找不到的值就是答案。 由于 \(\operatorn ......

P7795 典。 显然 \(\mathcal{O}(n ^ 2)\) 的时间复杂度无法通过。 使子段平均值最大，考虑二分。 可以二分平均值 \(mid\)，然后判断是否有满足条件的子段. 时间复杂度：\(\mathcal{O}(\dfrac{n\log\max\{a_i\}}{\text{eps}} ......

参考：1011. 在 D 天内送达包裹的能力;875. 爱吃香蕉的珂珂 leetcode 875: 珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。 珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉， ......

必须是1个有序的数组 第1次推导 public class test { public static void main(String[] args) { int[] ints = {1,2,3,5,7,9}; int a = 6; // 要查找的数 int i=0; //起始位置 int j=in ......

// 区间[l,r]被划分成[l,mid]和[mid+1,r]时使用int baserch_1(int l,int r){ while(l<r) { int mid = l + r>>1; if(check(mid)) r = mid; //check()判断mid是否满足性质 else l = m ......