中国空间站叫什么,徐州专业制作网站,seo线下培训课程,广州工程交易服务中心二分的本质是什么#xff1f;
很多人会认为单调性是二分的本质#xff0c;但其实其本质并非单调性#xff0c;只是说#xff0c;有单调性的可以进行二分#xff0c;但是有些题目没有单调性我们也可以进行二分。其本质其实是一个边界问题#xff0c;给定一个条件#xf…二分的本质是什么
很多人会认为单调性是二分的本质但其实其本质并非单调性只是说有单调性的可以进行二分但是有些题目没有单调性我们也可以进行二分。其本质其实是一个边界问题给定一个条件在我们的区间中有一部分满足这个条件有一部分不满足这个条件要求满足和不满足的边界值这个时候我们便可以使用二分来解决这个问题。
整数二分 基本步骤 1.先找到中间值mid 2.先判断mid是否满足性质check(mid) 3.若满足则缩小区间到[mid,r]lmid,不满足则反之 4.更新边界 区间前半部分边界点借用一下y总的画的图也就是红色区间的边界点 二分步骤 1.先找到中间值mid(lr1)/2 2.先判断mid是否满足红色区间的性质check(mid) 3.若满足则缩小区间到[mid,r]若不满足则[l,mid-1](rmid-1) 为什么要1
讲讲这里mid为什么要额外1,因为 当lr-1的时候因为除以二向下取整mid的值为l,如果check(mid)成功返回true则mid的值还是l并不会发生改变会造成死循环所以我们在后面1遇到这种情况发生时mid就变成了r避免了死循环的发生
模板如下
int bsearch_1(int l,int r){while(lr){int midlr11;if(check(mid)) lmid;else rmid-1;}return 1;
} 区间后半部分边界点也就是上图的绿色边界点 二分步骤 1.先找到中间值mid(lr)/2 2.先判断mid是否满足绿色区间的性质check(mid) 3.若满足则缩小区间到[l,mid]若不满足则[mid1,r](lmid1) 模板如下
int bserch_2(int l,int r){while(lr){int midlr1;if(check(mid)) rmid;else lmid1;}return 1;
}
这里以一个例题来解释一下用法
例题 给定一个按照升序排列的长度为 n 的整数数组以及 q个查询。
对于每个查询返回一个元素 k 的起始位置和终止位置位置从 0 开始计数。
如果数组中不存在该元素则返回 -1。
输入格式
第一行包含整数 n 和 q表示数组长度和询问个数。
第二行包含 n个整数均在 1∼10000 范围内表示完整数组。
接下来 q行每行包含一个整数 k表示一个询问元素。
输出格式
共 q行每行包含两个整数表示所求元素的起始位置和终止位置。
如果数组中不存在该元素则返回 -1 。
数据范围
1≤n≤100000 1≤q≤10000 1≤k≤10000
输入样例
6 3
1 2 2 3 3 4
3
4
5输出样例
3 4
5 5
-1 -1
