🍐二分的概念
我们通常说的二分一般分为：二分查找和二分答案。那它们有什么区别呢？其实二分答案和二分查找都是二分法的应用，但它们的操作不同。
🍊 二分查找：二分查找(Binary search)也称折半查找，是一种效率较高的查找方法。但是，二分查找要求线性表中的记录必须按关键码有序，并且必须采用顺序存储。
🍊 二分答案：二分答案主要用于求解一个函数的最小值或最大值，通常是在一个确定的范围内（例如给定函数的定义域），通过不断二分缩小答案的范围，最终得到一个最优解或最优解的近似值。
🍏二分查找
时间复杂度
- 二分查找最好时间复杂度是O(1)，最好情况下只需要进行1次比较就能找到目标元素。
- 二分查找最坏时间复杂度是：O(logn) ，最坏情况就是查找不到目标元素。
- 二分查找平均时间复杂度是：O(logn)。
例如我们要查找26，那么从根节点开始，一次就能搜到，那么我们随机挑选一位幸运儿，假如我运气不好，选到了16，那我也只需要以O(logn)的时间复杂度，以 26 22 15 16 的顺序找到它。
递归实现二分查找：
public static int binarySearchRecursive(int[] arr, int key, int low, int high){ if (low > high) { return -1; } int mid = (low + high)/2; if (key == arr[mid]) { return mid; } else if (key < arr[mid]) { return binarySearchRecursive(arr, key, low, mid-1); } else { return binarySearchRecursive(arr, key, mid+1, high); } }
非递归二分查找：
下面是一个简单的非递归二分查找代码实现示例： ```java public static int binarySearch(int[] arr, int target) { int low = 0; int high = arr.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { low = mid + 1; } else { high = mid - 1; } }
看了上述代码，你是否觉得太僵硬呆板？给你两个二分模板，保证嘎嘎上分！（这里是找的其他大佬的板子，确实好用。 我们大多时候就是判断不好边界条件，导致写二分的时候耗时太长，分情况来模板化代码，有利于我们长期记忆和加深理解。）
模板1： //第一个模板是尽量往左找目标 【只要是往左找答案，就用第一个模板，mid不用加一，r=mid，l加一；】 while (l < r){ int mid = l + r >> 1; //(l+r)/2 if (check(mid)) r = mid; // check()判断mid是否满足性质 else l = mid + 1; } 模板2： //第二个模板是尽量往右找目标 【只要是往右找答案，就用第二个模板，mid要加一，l=mid，r要减一；】 while (l < r){ int mid = l + r + 1 >> 1; //(l+r+1)/2 if (check(mid)) l = mid; else r = mid - 1; }
🥑题目示例
题目描述
输入格式
第一行 2 22 个整数 n nn 和 m mm，表示数字个数和询问次数。
第二行 n nn 个整数，表示这些待查询的数字。
第三行 m mm 个整数，表示询问这些数字的编号，从 1 11 开始编号。
输出格式
输出一行，m mm 个整数，以空格隔开，表示答案。
样例 #1
样例输入 #1
11 3 1 3 3 3 5 7 9 11 13 15 15 1 3 6 • 1 • 2 • 3
样例输出 #1
1 2 -1
提示
本题输入输出量较大，请使用较快的 IO 方式。
🥑思路：区间是有单调性的，查找第一次出现的位置，如果查到一个值比目标值大，就把右半边放弃，因为右半边肯定也比目标值大；同样，如果查到值比目标值小，那就放弃左半边。
import java.io.*; public class Main { static int N = (int) (1e6 + 10); static int[] a = new int[N]; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); static int nextInt() throws IOException { in.nextToken(); return (int) in.nval; } public static void main(String[] args) throws IOException { int n = nextInt(); int m = nextInt(); for (int i = 0; i < n; i++) { a[i] = nextInt(); } int l, r; while (m-- > 0) { int query = nextInt(); l = 0; r = n; while (l < r) { int mid = l + r >> 1; if (query <= a[mid]) r = mid;//因为是要找第一次出现的位置，那么这个等于号是一定要加上的，因为我们是从右往左找的，等于的时候有可能前面还有 else l = mid + 1; } if (a[r] == query) out.print(r + 1 + " ");//加一是因为问的序号而不是index else out.print(-1 + " "); } out.flush(); } }
题目背景
计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。
题目描述
现有 m mm 所学校，每所学校预计分数线是 a i a_ia
i
。有 n nn 位学生，估分分别为 b i b_ib
i
。
根据 n nn 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。
输入格式
第一行读入两个整数 m , n m,nm,n。m mm 表示学校数，n nn 表示学生数。
第二行共有 m mm 个数，表示 m mm 个学校的预计录取分数。第三行有 n nn 个数，表示 n nn 个学生的估分成绩。
输出格式
输出一行，为最小的不满度之和。
样例 #1
样例输入 #1
4 3 513 598 567 689 500 600 550 • 1 • 2 • 3
样例输出 #1
32
提示
数据范围：
对于 30 % 30\%30% 的数据，1 ≤ n , m ≤ 1000 1\leq n,m\leq10001≤n,m≤1000，估分和录取线 ≤ 10000 \leq10000≤10000；
对于 100 % 100\%100% 的数据，1 ≤ n , m ≤ 100000 1\leq n,m\leq1000001≤n,m≤100000，估分和录取线 ≤ 1000000 \leq 1000000≤1000000 且均为正整数。
🥑思路：要求估分和分数线相差最小，那肯定分数线刚超过估分或者估分刚超过分数线。我们就转化为，求第一个大于等于估分的分数线的位置。如此，这个位置的分数线或前一位置的分数线就是和估分相差最小的。
import java.io.*; import java.util.Arrays; public class Main { static int N = (int) (1e5 + 10); static int[] sch = new int[N]; static int[] stu = new int[N]; static int n, m, cnt; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); static int nextInt() throws IOException { in.nextToken(); return (int) in.nval; } public static void main(String[] args) throws IOException { n = nextInt(); m = nextInt(); for (int i = 0; i < n; i++) sch[i] = nextInt(); Arrays.sort(sch, 0, n); for (int i = 0; i < m; i++) stu[i] = nextInt(); //枚举学生 //正确做法：从右往左走，走不动了的那个数就是我们需要的第一个大于等于自身的数 for (int i = 0; i < m; i++) { int l = 0; int r = n; while (l < r) { int mid = l + r >> 1; if (sch[mid] >= stu[i]) r = mid; else l = mid + 1; } int abs1 = Integer.MAX_VALUE; int abs2 = Math.abs(stu[i] - sch[r]); if (r - 1 >= 0) abs1 = Math.abs(stu[i] - sch[r - 1]); cnt += Math.min(abs1, abs2); } out.println(cnt); out.flush(); //错误做法： // 错误原因： 由于我们要找第一个比他大的，那就应该是从右往左走， // 继续走的条件是大于等于它，如果不能继续走就说明我们已经到达了第一个点，而不是去找最后一个不符合条件的 /*for (int i = 0; i < m; i++) { //找出第一个学校分数线大于等于它的 //（注意：这里实际上找的是满足条件的前一个，因为我们的条件是不满足，所以退出的时候，返回的是最后一个不满足的值，满足的值在下一个） int l = 0; int r = n; while (l < r) { int mid = l + r + 1 >> 1; if (stu[i] > sch[mid]) l = mid; else r = mid - 1; } //比较当前分数线和前一个分数线与学生分数作差的abs大小 int abs1 = Integer.MAX_VALUE; int abs2 = Integer.MAX_VALUE; abs1 = Math.abs(stu[i] - sch[r]); if (r + 1 < n) abs2 = Math.abs(stu[i] - sch[r + 1]); if (abs1 != Integer.MAX_VALUE && abs2 != Integer.MAX_VALUE) cnt += Math.min(abs1, abs2); }*/ } }
🍏二分答案
如何判断一个题是不是用二分答案做的呢?
答案在一个区间内（一般情况下，区间会很大，暴力超时）
直接搜索不好搜，但是容易判断一个答案可行不可行
该区间对题目具有单调性，即：在区间中的值越大或越小，题目中的某个量对应增加或减少。
此外，可能还会有一个典型的特征： 求...最大值的最小 、 求...最小值的最大。
1、求...最大值的最小，我们二分答案（即二分最大值）的时候，判断条件满足后，尽量让答案往前来（即：让r=mid），对应模板1；
2、求...最小值的最大时，我们二分答案（即二分最小值）的时候，判断条件满足后，尽量让答案往后走（即：让l=mid），对应模板2；
题目背景
一年一度的“跳石头”比赛又要开始了!
题目描述
这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N NN 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。
为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M MM 块岩石（不能移走起点和终点的岩石）。
输入格式
第一行包含三个整数 L , N , M L,N,ML,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L ≥ 1 L \geq 1L≥1 且 N ≥ M ≥ 0 N \geq M \geq 0N≥M≥0。
接下来 N NN 行，每行一个整数，
表示第 i ii 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。
输出格式
一个整数，即最短跳跃距离的最大值。
样例 #1
样例输入 #1
25 5 2 2 11 14 17 21 • 1 • 2 • 3 • 4 • 5 • 6
样例输出 #1
4
提示
输入输出样例 1 说明
将与起点距离为 2 22和 14 1414 的两个岩石移走后,最短的跳跃距离为 4 44(从与起点距离 17 1717 的岩石跳到距离 21 2121 的岩石,或者从距离 21 2121 的岩石跳到终点)。
数据规模与约定
🥑思路：求最大？–> 模板2；（代码有注释）
我们二分的是最短距离，通过二分将这个最短距离（答案）最大化。如果能搬走的石头没超过规定的数量，那么我们还能继续尝试把答案开得更大一些。否则的话就说明我们开的长度太大了，要缩小一点。
import java.io.*; public class Main { static int N = (int) 5e4 + 10; static int len, n, m; static int[] a = new int[N];//每块岩石与起点的距离 从小到大 static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static void main(String[] args) throws IOException { len = nextInt(); n = nextInt(); m = nextInt(); for (int i = 0; i < n; i++) a[i] = nextInt(); int l = 0; int r = len; while (l < r) { int mid = l + r + 1 >> 1;//mid为答案 if (check(mid)) l = mid;//如果能搬走的石头没超过规定的数量，那么我们还能继续尝试把答案开得更大一些。 else r = mid - 1;//否则的话就说明我们开的长度太大了，要缩小一点 } System.out.println(r); } static boolean check(int mid) { int cnt = 0;//记录搬走了多少块岩石 int position = 0;//记录当前位置 for (int i = 0; i < n; i++) { if (a[i] - position < mid) cnt++;//如果从当前位置到岩石的位置长度小于mid则搬走，因为我们要找最大的最短跳跃长度 else position = a[i];//同理，如果从当前位置到岩石的位置长度比我们当前的答案大，那么我们就把当前岩石当作新的起点继续找下去。 } return cnt <= m;//没超出则返回true } static int nextInt() throws IOException { in.nextToken(); return (int) in.nval; } }
题目描述
对于给定的一个长度为N的正整数数列 
，现要将其分成
段，并要求每段连续，且每段和的最大值最小。
关于最大值最小：
例如一数列 4 2 4 5 1 要分成 3 段。
将其如下分段：
第一段和为 6，第 2 段和为 9 ，第 3 段和为 1，和最大值为 9。
将其如下分段：
第一段和为 4 ，第 2 段和为 6 ，第 3 段和为 6 ，和最大值为 6 。
并且无论如何分段，最大值不会小于 6 66。
所以可以得到要将数列 4 2 4 5 1 要分成 3 段，每段和的最大值最小为 6 。
输入格式
第 1 行包含两个正整数 N , M。
第 2 2行包含 N 个空格隔开的非负整数 
，含义如题目所述。
输出格式
一个正整数，即每段和最大值最小为多少。
样例 #1
样例输入 #1
5 3 4 2 4 5 1 • 1 • 2
样例输出 #1
6
提示
🥑思路：求最小值？ --> 模板1;
判断条件：要保证：每一段的和都小于等于最大值。也就是说，只要这一段的和加上下一个值大于最大值了，那下一个值加不得，得分段！接着段数++；
我们从第一个开始，把它自己当做一段，并且我们的左边界应该是数组里面最大的值（最大值至少也是自成一段），而右边界是全部数组数值相加（最大值最大就是全部加起来）。
import java.io.*; public class Main { static int N = (int) 1e5 + 10; static long n, m, l, r; static long[] a = new long[N]; static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public static void main(String[] args) throws IOException { n = nextLong(); m = nextLong(); for (int i = 0; i < n; i++) { a[i] = nextLong(); l = Math.max(l, a[i]); r += a[i]; } while (l < r) { long mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } System.out.println(r); } static boolean check(long mid) { long cnt = 1; long sum = a[0]; for (int i = 1; i < n; i++) { if (sum + a[i] > mid) { cnt++; sum = a[i]; } else sum += a[i]; } return cnt <= m; } static long nextLong() throws IOException { in.nextToken(); return (long) in.nval; } }
看完之后是不是对二分有了更深入的理解呢？ (*￣︶￣)❀
🐳结语
🐬初学一门技术时，总有些许的疑惑，别怕，它们是我们学习路上的点点繁星，帮助我们不断成长。
🐟文章部分语录摘自以下博文，因为其中的部分语录十分容易理解。希望对大家有帮助！
