南京网站建设 零云建站,wordpress无法上传歌曲,有企业信息的网站,上海网络推广招聘#x1f600;前言 二分查找是一种常见的算法技巧#xff0c;通过不断缩小搜索范围#xff0c;快速找到目标值的算法。在实际应用中#xff0c;二分查找可以应用于有序数组中的查找、求上界、求下界等问题#xff0c;具有较高的效率和广泛的应用价值。 #x1f3e0;个人主… 前言 二分查找是一种常见的算法技巧通过不断缩小搜索范围快速找到目标值的算法。在实际应用中二分查找可以应用于有序数组中的查找、求上界、求下界等问题具有较高的效率和广泛的应用价值。 个人主页尘觉主页 文章目录 算法基础--二分二分简介整数二分步骤入门例题二分查找一二分查找二二分查找三 总结 算法基础–二分
二分简介
二分分为整数二分和实数二分两种
整数二分步骤
找一个区间[L, R]使得答案一定在该区间中找一个判断条件使得该判断条件具有二段性并且答案一定是该二段性的分界点。分析中点M在该判断条件下是否成立如果 成立考虑答案在那个区间。如果不成立考虑答案在那个区间如果更新方式写的是R Mid则此时lmid1这是mid更新方式是 如果更新方式是lmid;则midlr11;c此时rmid-1
入门例题
二分查找一
蒜头君手上有个长度为 nn 的数组 AA。由于数组实在太大了所以蒜头君也不知道数组里面有什么数字所以蒜头君会经常询问整数 xx 是否在数组 AA 中。
输入格式 第一行输入两个整数 nn 和 mm分别表示数组的长度和查询的次数。
接下来一行有 nn 个整数 a_ia i 。
接下来 mm 行每行有 11 个整数 xx表示蒜头君询问的整数。
输出格式 对于每次查询如果可以找到输出YES否则输出NO。
数据范围 1≤n,m≤1e5 0≤x≤1e6
输出时每行末尾的多余空格不影响答案正确性
样例输入复制 10 5 1 1 1 2 3 5 5 7 8 9 0 1 4 9 10 样例输出复制 NO YES NO YES NO
#includecstdio
#includecstring
#includeiostream
#includealgorithmusing namespace std;
const int N1e510;
int num[N];
int n,m;int main(){cinnm;for(int i0;in;i)cinnum[i];sort(num,numn);while(m--){int t;cint;int l0,rn-1;while(lr){int midlr1; if(num[mid]t){rmid;}else{lmid1;}}if(num[l]!t){coutNOendl;}else{coutYESendl;}}return 0;
}二分查找二
蒜头君手上有个长度为 nn 的数组 AA。由于数组实在太大了所以蒜头君也不知道数组里面有什么数字所以蒜头君会经常询问在数组 AA 中大于等于 xx 的最小值是多大
输入格式 第一行输入两个整数 nn 和 mm分别表示数组的长度和查询的次数。
接下来一行有 nn 个整数 a_ia i 。
接下来 mm 行每行有 11 个整数 xx表示蒜头君询问的整数。
输出格式 对于每次查询如果可以找到输出这个整数。
否则输出 -1。
数据范围 1≤n,m≤1e5 0≤x≤1e6
输出时每行末尾的多余空格不影响答案正确性
样例输入复制 10 5 1 1 1 2 3 5 5 7 8 9 0 1 4 9 10 样例输出复制 1 1 5 9 -1
题解
#includecstdio
#includecstring
#includeiostream
#includealgorithmusing namespace std;
const int N1e610;
int n,m;
int num[N];
int main(){cinnm;for(int i0;in;i)cinnum[i];sort(num,numn);while(m--){int t;cint;int l0,rn-1;while(lr){int midlr1;if(num[mid]t){rmid;}else{lmid1;}}if(num[l]t){coutnum[l]endl;}else{cout-1endl;}}return 0;
}二分查找三
蒜头君手上有个长度为 nn 的数组 AA。由于数组实在太大了所以蒜头君也不知道数组里面有什么数字所以蒜头君会经常询问在数组 AA 中比 xx 大的最小值是多大但是这次蒜头君要求这个数字必须大于 xx不能等于 xx。
输入格式 第一行输入两个整数 nn 和 mm分别表示数组的长度和查询的次数。
接下来一行有 nn 个整数 a_ia i 。
接下来 mm 行每行有 11 个整数 xx表示蒜头君询问的整数。
输出格式 对于每次查询如果可以找到输出这个整数。
否则输出 -1−1。
数据范围 1≤n,m≤1e5 0≤x≤1e6
输出时每行末尾的多余空格不影响答案正确性
样例输入复制 10 5 1 1 1 2 3 5 5 7 8 9 0 1 4 9 10 样例输出复制 1 2 5 -1 -1
#includecstdio
#includecstring
#includeiostream
#includealgorithmusing namespace std;
const int N1e610;
int n,m;
int num[N];
int main(){cinnm;for(int i0;in;i)cinnum[i];sort(num,numn);while(m--){int t;cint;int l0,rn-1;while(lr){int midlr1;if(num[mid]t){rmid;}else{lmid1;}}if(num[l]t){coutnum[l]endl;}else{cout-1endl;}}return 0;
}总结
通过本文的介绍和例题演示我们深入了解了整数二分查找的基本原理及应用方法。在解决具体问题时首先要确定查找区间和判断条件然后利用二分思想不断缩小区间范围最终得到答案。同时我们也学习了如何处理特殊情况如查找大于等于某一值的最小值以及查找严格大于某一值的最小值等情况。
热门专栏推荐 想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集 linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
欢迎大家加入我的社区 尘觉社区 文章到这里就结束了如果有什么疑问的地方请指出诸佬们一起来评论区一起讨论 希望能和诸佬们一起努力今后我们一起观看感谢您的阅读 如果帮助到您不妨3连支持一下创造不易您们的支持是我的动力
