目录一.前言二.二分查找1.介绍2.注意点3.模版1left,right写法2[left,right]写法3[left,right)写法三.例题题目描述输入输出样例四.二分答案五.例题题目描述输入输出样例六.感言一.前言二分查找看起来很简单也很容易理解。但细节特别多写法也各不相同想要正确实现实属不易。二.二分查找1.介绍二分查找是一种在有序数组中快速查找目标值的算法。它的核心思想是每次通过比较中间元素将查找范围缩小一半因此效率非常高。2.注意点二分查找的核心思想主要是查找区间范围不同写法在书写时最主要遵循的就是区间范围。例如左闭右闭[left, right]写法依据查找区间两端都包含在候选范围内 循环条件必须用 因为最终lr时符合区间定义还有一个元素要查找在更新l,r左右指针时当 arr[mid]x说明mid以及它左边的所有元素都小于目标因此新的左边界应设为l mid1。循环结束后一定有left right即left right 1。此时right 指向最后一个小于 x 的位置left 指向第一个大于 x 的位置3.模版常见有三种写法有左闭右开左闭右闭和左开右开三种写法。对于一个有序数列如1 2 3 3 3 5 6会完成四种常见操作对于查询元素x3,我们需要寻找x的最后一个位置,x的第一个位置,x的最后一个位置,x的第一个位置这里主要介绍左开右开的写法1left,right写法我们可以把查找区间看做两部分分界线是由条件决定的如下代码可以得到上述例子上2与3的边界初始化定义l与r按照开区间定义。#includeiostream using namespace std; const int N1e710; int a[N]; int main(){ int n; cinn; for(int i1;in;i){ cina[i]; } sort(a1,an1); int rn1,l0; int x; cinx; while(l1r){ //查询左边界两侧值可以把边界看做一个竖线 把区间划分为两部分 int mid(r-l)/2l; if(a[mid]x){ rmid; } else{ lmid; } } coutl:l r:rendl; //无论是否存在x这一查询值最后l位于小于x的最后一位r位于大于等于x的第一位 if(rna[r]x) {coutYES endl; //如果x大于所有值rn1,a[n1]未初始化需要加上判断条件 并且写在前面 cout小于x的最后一位数下标为lendl; cout大于等于x的第一位数下标为: rendl; } else coutNO该值不存在endl; return 0; }优点很明显边界处理简单不需要写mid1、mid-1也不需要考虑right n还是n-1不会发生死循环mid永远不会等于l或r因为(lr)/2在整数除法下当l1r时mid严格在l和r之间简单解决多种变体稍改判断条件即可实现不同的要求2[left,right]写法int l 0, r n - 1; // 右边界包含在内 while (l r) { // 区间非空 int mid l (r - l) / 2; if (arr[mid] x) return mid; else if (arr[mid] x) l mid 1; else r mid - 1; } return -1; // 未找到边界更新必须要1-1否则会死循环3[left,right)写法int l 0, r n; // 右边界不包含 while (l r) { // 区间非空 int mid l (r - l) / 2; if (arr[mid] x) return mid; else if (arr[mid] x) l mid 1; else r mid; // 注意不是 mid-1 } return -1;当 arr[mid]x 时rmid因为右开mid 已被排除三.例题题目描述有 n个数n≤1000000这 n 个数已按从大到小顺序存放在一个数组中然后有 T 次查询每次输入一个数要求用折半查找法找出该数在数组中第一次出现的位置。如果不在数组中输出 0。输入第一行数组元素的个数 n第二行 n个数组元素的值。第三行输入查询次数 TT≤100000往下有 T 行每行输入一个需要查询的数字。输出查找的值在数组中的位置。输入输出样例样例输入 #110 10 9 8 7 6 5 4 3 2 1 2 9 5样例输出 #12 6代码#include bits/stdc.h using namespace std; const int N1e710; int arr[N]; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cinn; for(int i0;in;i){ cinarr[i]; } int t; cint; while(t--){ int num; cinnum; int l0,rn-1,mid; while(lr) { mid(r-l)/2l; if (arr[mid] num) r mid; else lmid1; } if(arr[l]num) coutl1\n; else cout0\n; } return 0; }四.二分答案二分答案是一种通过二分法在值域上搜索满足某种条件的解的方法常用于求解最优化问题如“最大值的最小值” “最小值的最大值”或判定性问题是否存在某个值使得条件成立。其核心思想是将求解问题转化为判定问题——对于候选答案 判断它是否可行然后根据单调性缩小答案范围。步骤为确定答案区间写出二分查找写出check(mid)函数(时间复杂度通常为 O(n) 或 O(n log n)五.例题题目描述农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100000) 天里每天需要的开销。约翰打算为连续的 M (1 ≤ M ≤ N) 个财政周期创建预算案他把一个财政周期命名为 fajo 月。每个 fajo 月包含一天或连续的多天每天被恰好包含在一个 fajo 月里。约翰的目标是合理安排每个 fajo 月包含的天数使得开销最多的 fajo 月的开销尽可能少输入第一行包含两个整数 NM 用单个空格隔开。 接下来 N行每行包含一个 1 到 10000 之间的整数按顺序给出接下来 N 天里每天的开销。输出一个整数即最大月度开销的最小值。输入输出样例样例输入 #17 5 100 400 300 100 500 101 400样例输出 #1500代码#include iostream #include algorithm const int N1e7; int n,m; using namespace std; int arr[N]; bool check(int x){ //贪心策略每个周期尽可能达到开销上限一旦周期数超过m //则说明无论如何调整也无法m int cnt1; int sum0; for(int i0;in;i){ if(sumarr[i]x){ cnt; sumarr[i]; if(cntm) return false; }else{ sumarr[i]; } } return true; } int main(int argc, char** argv) { cinnm; int maxday0,total0; for(int i0;in;i) { cinarr[i]; maxdaymax(maxday,arr[i]); totalarr[i]; }//开销越大贪心策略划分的财政周期数量越少 但可以调整为m个可行 //开销太小划分的财政周期会超过m,不可行 //答案区间为[maxday,total]区间 int lmaxday-1,rtotal1; while(l1r){ int mid(lr)/2; if(check(mid)){ //check函数最关键 rmid; } else{ lmid; } } coutr; //求最大值最小化最终r指向的为答案 return 0; }六.感言每次一忙起来就会想什么也不做只想一个人静静的待着。这次的笔记是好不容易抽出时间整理的算是做一个小总结给自己的学习一个交代。如有不当欢迎各位大佬的指正。