二分法

二分查找 #include <stdio.h> int main(void) { int arr[] = {-2, -1, 0, 1, 2, 3}; //数组 int l = 0; int r = sizeof (arr) / sizeof(int) - 1; //计算数组的大小，然后 - 1就是最 ......

二分查找需要满足的条件： 用于查找的内容逻辑上来说是需要有序的 找的数量只能是一个，而不是多个 查找的区间 左闭右闭 [ left, right ] 左闭右开 [ left, right ) 闭区间：是直线上介于固定两点间的所有点的集合（包括给定的两点），用 [a，b]来表示 (包含两个端点a和b） ......

图论——二分图 学习笔记 定义 二分图，又称二部图，英文名叫 Bipartite graph。 定义为，一个图，可以将节点划分为两个集合，而集合内部没有相连的边。如图： 性质 如果对二分图黑白染色，那么每条边两边对应的一定是一个黑点、一个白点； 不存在长度为奇数的环，因为只有偶数条边，才能从一个集合 ......

1、二分查找法只适用于从有序的数列中进行查找(比如数字和字母等)，将数列排序后再进行查找 2、二分查找法的运行时间为对数时间O(㏒₂n) ，即查找到需要的目标位置最多只需要㏒₂n步，假设从[0,99]的队列(100个数，即n=100)中寻到目标数30，则需要查找步数为㏒₂100 , 即最多需要查找7 ......

sto louis & Maverik orz! 写一些知识点，图论杂题过后单独开一篇。 最小割 最大流最小割定理 对于任意网络 \(G = (V, E)\) ，其上的最大流 \(f\) 和最小割 \(\{S, T\}\) 总是满足 \(|f| = ||S, T||\) 。 即，最大流在数值上等于最 ......

蓝桥杯管道 -- 二分, 区间覆盖 原题链接 参照执梗大佬的代码, 我太菜了wuwuwu...... import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.S ......

定义 如果一张无向图可以分为两个集合，并且两集合内部的店没有边相连，则称该图为二分图。 判定 染色法 任意选择一个点开始染色，将与它相连的点染上相反的颜色，当出现矛盾时，说明不是二分图，否则为二分图。 二分图的最大匹配 定义 匹配：设 G 为二分图，若其子图 M 满足任意两条边之间无公共节点，则为二 ......

1. 判定 （染色法） #include<bits/stdc++.h> using namespace std; const int N = 100010, M = 200010; int n, m; int g[N], cnt, color[N]; struct node{ int nxt,to; ......

一、题目 力扣链接：https://leetcode.cn/problems/binary-search/description/ 二、解法思路 标准的二分查找题目，常规上有左闭右闭和左闭右开的解法 1、左闭右闭 class Solution: """ leetcode:704 采用左闭右闭的方式， ......

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 示例 1: 输入: nums = [1,3,5,6], target = 5 输出: 2 示例 2: 输入: nums = [ ......

使用场景 询问的答案具有可二分性（对于单个询问可以二分答案） 题目允许使用离线算法 修改对判定答案的贡献互相独立，修改之间互不影响效果 修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值 贡献满足交换律，结合律，具有可加性 实现 对答案所在的值域进行二分，记录值域区间 \([l,r]\)， ......

作用 求二分图中最大匹配，\(O(n\times(n+m))\)。 代码 inline bool dfs(int u){ for(int v:G[u]){ if(!vis[v]){ vis[v]=1; if(!link[v]||dfs(link[v])) return link[v]=u,1; } ......

2023-11-11：用go语言，字符串哈希+二分的例题。 给定长为 n 的源串 s，以及长度为 m 的模式串 p， 要求查找源串中有多少子串与模式串匹配， s' 与 s 匹配，当且仅当 s' 与 s 长度相同，且最多有 k 个位置字符不同。 其中 1 <= n, m <= 10^6，0 <= k ......

二分查找模板总结（区间、条件不再纠结） 二分查找是一种在 有序数组 中查找某一特定元素的搜索算法。元素集合有顺序，元素性质有分界点，二分法就可以用来求分界点，并不一定要求集合中元素是不重复的。 算法思路：假设目标值在闭区间 [left, right] 中， 每次将区间长度缩小一半，当 left = ......

刷 Leetcode 总能遇到关于二分的题目，但是之前也只是草草地了解一下，每次在使用的时候都需要找模板，要不然就需要对于边界条件进行调试，着实是很麻烦！！！ 二分介绍： 首先来简单介绍一下二分：二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求 线性 ......

数组基础理论 数组是存放在连续内存空间上的相同类型数据的集合。 可以通过下标轻松获取数据，但是增删元素的时候需要移动其他元素 Vector和array的区别 vector的底层实现是array,但是vector是容器不是数组 数组的元素不能删除，只能覆盖 小技巧：取中间 int mid =l+r>> ......

int binarysearch(int *arr, int n, int a)//n-元素总个数，a-目标元素{ int left = 0; int right = n + 1; while (right - left != 1) { int mid; mid = (left + right) / ......

一些定理 一、最小点覆盖=最大匹配 即，选一些点染色，要求图中所有边至少有一端被染色。 证明： 涂色方案：设匹配点为红点，未匹配点为蓝点。易知，一对匹配的红点，最多只有一个点会连接蓝点。将这个连接了蓝点的点染色。 合法性：所有匹配边显然已经合法了，考虑非匹配边。非匹配边有一个性质：它至少与一条匹配边 ......

/** * https://leetcode.cn/problems/find-peak-element/description/ * 由于数组的两个端点前后都是负无穷，所以给定一个i如果arr[i]>arr[i+1]说明在[0，i]这个区间里面一定有个峰值 * 反之则在[i,n]之间 * 以此使用 ......

/** * https://leetcode.cn/problems/search-in-rotated-sorted-array/description/ * 找到旋转的点 * 判断target的值是在旋转点的那一边 * 在在这个区间内使用二分查找 * */ public static void ......

/** * https://leetcode.cn/problems/search-a-2d-matrix/description/ * * @return*/ public static boolean hanShu3(int[][] matrix, int target){ int m = ma ......

int s(int shuzu[], int len, int x) { int low = 0, hight = len - 1, mid; while (low<=hight) { mid = (low + hight) / 2; if (shuzu[mid] == x) return shuz ......

二分图·博弈 顾名思义 : 二分图 + 博弈 二分图 首先先知道一些基本方法： 求出二分图最大匹配所必须的点或边，就是求去掉这个点（边）过后最大匹配还是不是原来的最大匹配。 复杂度更优的方法是先跑一遍 Dinic 求出最大流的任意解与这种解下每条边的残量。分别从原点、汇点开始 tarjan 残量不为 ......

一、二分查找 其本质就是找一个区间 二、整数二分 2.1. 查找左边界的模板 int findPrior(int left,int right,int target) { while (left < right) { int mid = (left + right) / 2; if (a[mid] ......

WQS 二分 大概弄懂了是要处理怎么样的问题，以及一般处理张什么样。 形式 一般来说是要处理刚好有 \(k\) 个的问题。 并且选择 \(i\) 个的时候整个问题的代价是凸的。 一般来说通过 \(wqs\) 二分之后直接当做没有限制的方法去做就好了。 做法 设 \(f(i)\) 为选 \(i\) 个 ......

当且仅当图中不含奇数环 由于图中没有奇数环，所以染色过程没有矛盾 染色法 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=100010,M=200010; int n, ......

二分图博弈 什么是二分图博弈： 两个人博弈，每一次自己结束一定会轮到对方，并且自己某个状态选择后对方可以选择的状态是一个区间。 结论： 二分图博弈，作为起点的一方要是选择状态 \(P\)，若状态 \(P\) 一定在最大匹配上，则先手必胜，反之，先手必败。 这里的胜败表示的是“不能继续转移的人”失败。 ......

下面展示python代码 def binary_search(my_list, item): low = 0 high = len(my_list) - 1 while low <= high: mid = (low + high) // 2 guess = my_list[mid] if gues ......

0.前言 整体二分算法在一定程度上推翻了本蒟蒻之前学习的一些内容、颠覆了本蒟蒻的认知、打开了全新世界的大门。故本蒟蒻认为有必要写个博客记录一下。 1.问题引入 1.1 有一道非常简单的题目： 例一、求区间内第 \(k\) 小的数 给出 \(a_1\sim a_n\)，求 \(a_l\sim a_r\ ......

左闭右闭区间：（另一种为左闭右开区间） 注意middle的取值 class Solution { public int search(int[] nums, int target) { //首先关于（left + rigth)/2 取舍问题：int类型数据作除法会舍去小数部分 int left = ......