二分法

Focal交叉熵： 上面式子是一个交叉熵的改进版本，多了一个权重系数pos_weight，表示图像中，正例、负例的比例，那个越少，就越重视哪一个。好好感受下，loss|y_pred = 0.8 loss|y_pred = 0.2应该是“相等”的，这是上面式子设计的初衷！ 下面是Focal loss的 ......

题目描述： 某一天，老鼠杰瑞抓住了一个机会，成功的到达了冰箱的附近，正当杰瑞打开冰箱门，想要享受美味的奶酪的时候，没想到冰箱里的奶酪太多了，奶酪洒了一地。汤姆猫听到了这个动静，正在火速赶往冰箱想要抓住杰瑞。杰瑞凭借与汤姆多年对抗的经历，仅凭借汤姆的脚步声便能推断汤姆还有多久抵达，现在，杰瑞并不怕汤姆 ......

原题链接 二分查找中的mid+1和mid-1的问题 二分查找中的边界问题处理不好很容易导致死循环和计算错误的问题，以题目 数的范围为例。 题目大意 ​ 二分查找重复数第一次出现的位置和最后一次出现的位置。 数学含义 ​ 第一次位置即 找到 一个长度最大的 >=X 区间的 左边界 ​ 最后一次位置即 ......

int search(int* nums, int numsSize, int target){ int left = 0; int right = numsSize - 1; int middle; while (left <= right){ middle = (left + right) / ......

【深基13.例1】查找 题目描述 输入 \(n\) 个不超过 \(10^9\) 的单调不减的（就是后面的数字不小于前面的数字）非负整数 \(a_1,a_2,\dots,a_{n}\)，然后进行 \(m\) 次询问。对于每次询问，给出一个整数 \(q\)，要求输出这个数字在序列中第一次出现的编号，如果 ......

注意事项 一般 check 函数只能判断是否合法，没有等于这个概念。所以下面两个例子虽然可以通过改变判断符号进行相互转化，但实际问题是不行的。 最大值最小 给定一个不降的序列 \(a\)，查找其中大于等于 \(x\) 的第一个数。 其实就是查找第一个合法的点。 while(l<r) { mid=(l ......

前言 可能有粗心写的不正确的地方，或者因为技术有限写得不好的地方，欢迎大家批评指正，文章中给出的代码是本人自己写的leetcode中的代码，是代码的核心部分，如果放到本地编译器中，可能要加入mian()函数等内容。 题目1 二分查找 LeetCode704二分查找 题目要点 二分查找的思路非常简单， ......

704.二分查找 思路：二分查找的前置条件是数组有序且无重复元素，每次通过改变边界值来缩小查找范围。 自己写的: 可以看到对边界的判断存在问题，基本思路是左闭右闭，但是while循环的判断是按照左闭右开来写的。对于数组中仅包含一个元素且该元素是目标函数的情况会出错。重新调试后添加了一个low==hi ......

有 n 个线性序列，第 i 个序列可以表示成 ki×x+bi 的形式 (x=0,1,2,... )。 请问将这些序列中的数按从小到大的顺序合并起来，前 m 个数分别是多少（重复出现的数合并后也会出现多次）？ 输入格式 第一行一个整数 n 。 接下来 n 行每行两个整数 ki，bi 。 最后一行一个整 ......

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。它的基本思想是将目标值与数组中间的元素进行比较，如果目标值小于中间元素，则在数组的左半部分继续查找，否则在右半部分查找，不断缩小搜索范围，直到找到目标值或确定目标值不存在为止。 二分查找也叫折半查找，比如在一个有序的数组 ......

⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭与你分享每场 LeetCode ......

最小点覆盖： 定义：选择最少的点，使得每条边都有一端被选。 结论：二分图的最小点覆盖等于二分图最大匹配 构造方案：从所有左侧未匹配的点出发，先走一条未匹配边，然后走一条匹配边，把所有走过的点标记，选择左边所有未标记的点和右边所有标记的点。 最大独立集 定义：选择最多的点，使得他们之间两两没有边。 结 ......

1、整数二分 以acwing 789为例，题目要求如下： 第一行输入整数n和q，表示数组长度和询问个数。 第二行输入数组，包含n个整数。 接下来q行，每一行一个整数k，表示一个问询元素。 要求输出q行，每行包含两个整数，表示所求元素的起始位置和终止位置。 如果数组中不存在该元素，则返回 -1 -1。 ......

Day1-数组2023.5.20 2023.9.14二刷 Leetcode704 二分查找 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 初解 已经不记得二分查找了，遍历找\ ......

l.sort()def index(l, target_num): if len(l) == 0: print('没找到') return middle_index = len(l) // 2 if l[middle_index] < target_num: l_right = l[middle_i ......

cdq 分治 基本思想 我们要解决一系列问题，这些问题一般包含修改和查询操作，可以把这些问题排成一个序列，用一个区间[L,R]表示。 分。递归处理左边区间 \([L,M]\) 和右边区间 \([M+1,R]\) 的问题。 治。合并两个子问题，同时考虑到 \([L,M]\) 内的修改对 \([M+1, ......

## 浮点数二分 ~~~c++ int test(int l,int r) { double x; cin>>x; double l = 0,r = x; while(r - l<1e-6) { double mid = (l+r)/2; if(check(mid)) r = mid; else l ......

1 # 二分 2 3 ## 整数二分 4 5 ~~~c++ 6 //区间[l,r]被划分成[l,mid]和[mid+1,r]时使用 7 int test01(int l,int r) 8 { 9 while(l<r) 10 { 11 int mid = (l+r)/2; 12 bool check( ......

#include<iostream>using namespace std; // 可以递归调用的二分查找int search(const int(&a)[10], int start, int end, int target){ // 基准情况：目标值超出范围，或者start > end，说明没有 ......

Cars 二分图染色/拓扑排序 题意 坐标轴 $X$ 上有 $n$ 辆汽车。每辆车最初位于一个整数点，并且没有两辆车位于同一点。此外，每辆车都可以向左或向右定向地、可以随时以任何恒定的正速度地沿该方向移动。定义两种关系： 如果两辆汽车无论速度如何都永远不会到达同一点，我们称它们为 无关紧要的。换句话 ......

递归函数 """ 递归：直接或者间接的调用其他函数 """ def index(): print('from index') func() def func(): print('from func') index() func() ##### 递归在实际编码中是不允许出现的，一旦出现了无限递归就会直 ......

定义 wqs 二分一般解决恰好选 \(m\) 个的问题，且关于 \(m\) 的函数 \(f(m)\) 为凸函数（\(f(m)\) 表示恰好选 \(m\) 个的最优解）。 上图为 \(f(m)\) 函数。 二分斜率 \(k\)，假设每选一次都要减去 \(k\)，则 \(f'(x)=f(x)-kx\)， ......

二分优点,加快在有序数列中,蓝红区域的扩展,朴素算法缓慢进行.如何扩展,用灰色区域 的中点来判断,然后扩展颜色区域,灰色区域会不断减少,只要logn次就能把灰色区域长度 缩小为0 l在哪里,哪里就是蓝色,r同理,假设没有蓝色区域,赋值0(保留了一个位置)会导致,扩展过程中,红色一直扩展 直到两者相遇 ......

以下是一个Python实现的简单二分查找算法的代码示例： def binary_search(arr, target): left, right = 0, len(arr) - 1 while left <= right: mid = (left + right) // 2 # 找到中间元素的索引 ......

10 二分 近3年考察： 题号 题型 分值 2021 第20题 完善程序 15分 2022 第18题 阅读程序 15分 :::info 2023年备考建议 二分查找又称为折半查找，对已排序的数组，重复执行“将目标数据和数组中间的数据进行比较后将查找范围减半”的操作，直到找到目标数据或其不存在。 理解 ......

## WQS二分学习笔记 [toc] ### 用途： WQS二分通常用来解决形如强制选k个且收益最大/代价最小的题目。 就比如说：https://www.luogu.com.cn/problem/P5308 如果没有限制的话，代码会非常简单 ### 思考方式： #### 使用限制： 首先要使用WQS ......

//1int binarySearch(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int mid = left + (right - left ......

有一些题目需要用到二分，但多次询问直接二分，会导致 TLE，那么就需要用到一个离线算法，将多个询问放在一起二分，这就是整体二分。 ### 条件 能够用整体二分解决的题目需要满足以下性质： 1.题目具有可二分性（即单调性）； 2.**修改对判定答案的贡献相互独立**，修改之间互不影响效果。 3.修改如 ......

# 数组 ## 704.二分查找 mydemo ```c++ class Solution { public: int search(vector& nums, int target) { int len = nums.size(); //cout target) { right = mid - 1 ......

二分法的适用场景 1. 有单调性的题目一定可以二分 2. 没有单调性也有可能二分 由此可见，二分的核心并不是单调性。 核心是：定义了某种性质，使得可以将整个数据集一分为二，左半边满足一种性质，右半边不满足；右半边满足另一种性质，左半边不满足。则二分可以寻找左区间的边界，也可以寻找右区间的边界。 二分 ......