二分

需求：比如说查询一个班级大于60分的最低分等等。 思路与二分法基本相同，只不过是对比的逻辑发生了一些小变化，这里所说的上界就是指大于某个值的最小下标。 当mid < target ：说明 target 的上界还在mid的右边，所以要去找比mid大的 当mid > target：说明 mid 有可能是 ......

# 普及组基础算法 这些都是零零散散接触过的基础算法，写个笔记把这些整理到一起来。 ## 线性降维技巧 之前在学校洛谷团队里看到一个[题单](https://www.luogu.com.cn/training/263558)，觉得这些技巧可能有用，就转存了。 ### 前缀和 差分 前缀和是一种对区间 ......

# 二分答案 - 貌似题目让你求啥就要对什么东西进行二分 ## 实数二分 1. 注意精度，如果要求输出两位小数，建议二分到三、四位 2. 还是注意精度，P1542不用 long double 都过不去 ### [P1024 [NOIP2001 提高组] 一元三次方程求解](https://www.l ......

题目大意: n 个商店在 一条直线上, 有一个xi 然后 有 ai 个商品 你可以把 商店的物品 移动到另一个商店, 代价为 : abs(xi-xj) 在代价不超过T的情况下 你可以选择一个商店来让 其他商店的物品都移到这个商店,问最多移动多少个物品 思路: 双指针维护一个最大的区间, 因为这个最大 ......

题目链接：https://www.luogu.com.cn/problem/P3168 题解： 主席树可以解决一类j静态区间第 $k$ 小的[问题](https://www.luogu.com.cn/problem/P3834)，我们先来看看这是怎么工作的 - 主席树的本质就是有很多棵线段树，然后发 ......

【题面】 你决定用素数定理来做一个调查. 众所周知, 素数又被称为质数，其含义就是除了数字一和本身之外不能被其他任何的数字除尽. 现在给定一个正整数序列 ,+1,⋯ ,a,a+1,⋯,b (≤)(a≤b), 请找出一个最小值 l, 使其满足对于任意一个长度为 l 的子串, 都包含 k 个质数. 找到 ......

# 二分 ## 目录 Content - 概述 - 实现与细节 - 问题与思考 - 经典应用：二分查找 - 经典应用：二分答案 ## Part 1 概述 ### I.二分是什么 >二分是分治思想的应用，二分通过把问题分成两半，借助题目中的单调性抛弃一半的问题，从而节省时间。故时间复杂度往往是$O(l ......

之前的二分大多数都是整数类型的,今天又学到一种新型的二分,浮点数的二分,浮点数的二分可太巧妙了.且听我细细分说::OpenJudge - 2018:Best Cow Fences #include<bits/stdc++.h> using namespace std; const int N=1e5 ......

1.在列表中获取中间位置的值 2.将中间值和所需要查找的值做对比, 如果相等则返回中间值的位置 3.如果中间值小于所需要查找的值, 则将查找范围缩小到 left 至 mid-1 (即right 修改为 mid-1) 4.如果中间值大于所需要查找的值, 则将查找范围修改为 mid+1 至 right ......

# 概念 对于一个很多询问的题，假如对于一个询问可以二分处理，同时一次 check 可以只用 $n$ 的时间处理所有询问的 check 结果，我们可以使用整体二分来做这个题。 # 思想 设函数 $\operatorname{solve}(S, L, R)$ 为现在正在处理询问序列 $S$ 里的询问， ......

[TOC] ## T1 [Daimayuan] 一半相等（C++，数学） 给定 $n$ （$n$ 为偶数）个整数数组 $a_1,a_2,…,a_n$ 考虑这样的一个 $k$，每次操作选定一个 $i$，将 $a_i$ 减少 $k$，执行多次（可能 $0$ 次）后使得数组中至少有一半的元素相等，求最大的 ......

概述 二分答案即利用二分查找来得到答案，一般情况下，左边界 $left$ 是 $0$ 或者 $1$；右边界 $right$ 则视题目条件而定，取一个很大的数，然后利用二分查找的思想，来找到答案。 二分答案的要求 如果题目能够使用二分答案的思想来解决，那么 $[left, right]$ 范围内，要满 ......

一、基本查找 package com.itheima.d8_sort_binarysearch; /** *基本查找 */ import java.util.Scanner; public class Test3 { public static void main(String[] args) { ......

概述 二分答案即利用二分查找来得到答案，一般情况下，左边界 $left$ 是 $0$ 或者 $1$；右边界 $right$ 则视题目条件而定，取一个很大的数，然后利用二分查找的思想，来找到答案。 二分答案的要求 如果题目能够使用二分答案的思想来解决，那么 $[left, right]$ 范围内，要满 ......

# 1 逻辑回归的简介 ## 1.1 简介 **逻辑回归（Logistic Regression）是机器学习中的一种分类模型，逻辑回归是一种分类算法，虽然名字中带有回归，但是它与回归之间有一定的联系。由于算法的简单和高效，在实际中应用非常广泛。** ## 1.2 应用场景 - 广告点击率（是否会被点 ......

不明白为什么还有神笔在中考前一周故意恶心我啊。 在搞心态和文化课之间，我选择 OI。 ### $$\large\textbf{整体二分}$$ #### [MET-Meteors](https://www.luogu.com.cn/problem/P3806) $\mathtt{[C|5.0]}$ 长 ......

# 1 算法原理 **适用条件：有序数组** # 2 算法模板 ```python class Solution: def search(self, nums: List[int], target: int) -> int: left = 0 right = len(nums) - 1 # 规则 [ ......

题目大意： 给定两个整数 $a(2 \le a \le 2 \times 10^9)$ 和 $b(1 \le b \le 10^{18})$。 判断是否存在两个正整数 $x$ 和 $y$，同时满足如下两个条件： 1. $x + y = a$ 2. $x \times y = b$ 解题思路： 用 $ ......

1、概念：在一些有序的或无序的数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程叫做查找，也就是给定一个值，在查找表中确定一个关键字等于给定值的记录或数据元素。 2、平均查找长度（后期可能会增加） 3、查找长度分为成功和失败两种 4、顺序查找 1、主要思想：将查找值顺序逐个与结点值进行比 ......

# 【小心地雷！】关于二分方法的不同与代码细节 ~~笔者写[这道题](https://www.luogu.com.cn/problem/AT_agc033_d "这道题")，调了30min发现二分挂了qwq，故作此文。~~ 众所周知，一般情况下，二分的方式有两种： 1.区间收缩方式是$l = mid ......

#include <bits/stdc++.h> using namespace std; int main(int argc, char** argv) { int max=100,min=0; string b; cout<<"请你想一个数1~100"<<endl; system("pause" ......

Matrix 题意：给你一个n * n的矩阵，矩阵一点的值是i^2 + 100000 × i + j^2 - 100000 × j + i × j，问在整个矩阵中第ｍ大的值是多少。 //想分解公式但是什么都没看出来，这个公式是用于判断单调性的 //主函数里面二分答案，check二分查找有多少个小于当 ......

第N遍做这个题 这题也写过很多次了还是有点费劲。需要回忆。用时14min。 ......

[TOC] # 简介 # 应用 ## 应用1：Leetcode ### 题目 [33. 搜索旋转排序数组](https://leetcode.cn/problems/search-in-rotated-sorted-array/) ### 分析 #### 方法一 旋转后的数组，就形成了两个有序的子数 ......

# 算法 in Go：Binary Search（二分查找） ## Binary Search（二分查找） ### Binary Search（二分查找） - 猜数 - 1、2、3、4、5、6、7、8 - 排好序一个集合，先从中间开始猜，根据提示就可以排除一半，在剩余的一半里，再从中间开始猜，依此类 ......

### 思路 二分法的前提是**数组有序**。另外，当数组中存在重复元素时，最后返回的下标可能不唯一，具体实现不同，可能导致最后结果也不同。 ![image](https://img2023.cnblogs.com/blog/3195987/202306/3195987-20230605174837 ......

## 使用条件 1. 有序数组 2. 元素不重复 ## 区间设置 1. 左闭右闭： - 左右区间边界都要在数组的索引有效范围内（left=0,right=数组长度-1） - 判断条件 left(左边界)nums[n]){ left=n+1;//当前元素的值不满足，缩小区间 }else if(targ ......

存在一个 **无向图** ，图中有 $n$ 个节点。其中每个节点都有一个介于 $0$ 到 $n - 1$ 之间的唯一编号。给你一个二维数组 $graph$ ，其中 $graph[u]$ 是一个节点数组，由节点 $u$ 的邻接节点组成。形式上，对于 $graph[u]$ 中的每个 $v$ ，都存在一条 ......

>二分查找 ```c #include int binary_search(int *a,int p,int q,int ele) { int mid=0; if(p>q) { return 0; } mid=p+(q-p)/2; if(ele==a[mid]) { return mid; } if ......

[toc] # 二分法 > 二分法思路 1.二分法的使用前提条件：列表中得数字必须要有序 2.将对象整除2分成两部分 3.将目标数值与分割后的对象做比较来确定目标数值在哪一部分 4.继续重复这两个步骤直至找到目标数值 * 例 ``` # 判断此表中是否有20这个数 l = [1, 22, 44, 1 ......