站群管理系统cms,北京都有哪些公司名称,江西邮电建设工程有限公司网站,上海公关公司排名整数二分算法和浮点数二分算法 二分
现实中运用到二分的就是猜数字的游戏 假如有A同学说B同学所说数的大小#xff0c;B同学要在1~100中间猜中数字65#xff0c;当B同学每次说的数都是范围的一半时这就算是一个二分查找的过程
二分查找的前提是这个数字序列要有单调性
基…整数二分算法和浮点数二分算法 二分
现实中运用到二分的就是猜数字的游戏 假如有A同学说B同学所说数的大小B同学要在1~100中间猜中数字65当B同学每次说的数都是范围的一半时这就算是一个二分查找的过程
二分查找的前提是这个数字序列要有单调性
基本步骤
初始化
设定两个指针left 和 right分别指向数组的起始和末尾。
计算中间位置
使用公式 mid left (right - left) / 2 或者leftright1计算中间位置。
比较
如果中间位置的元素等于目标值返回中间位置。 如果目标值小于中间位置的元素则将 right 更新为 mid - 1继续在左半部分查找。 如果目标值大于中间位置的元素则将 left 更新为 mid 1继续在右半部分查找。
重复
重复步骤 2 和 3直到 left 超过 right。
结束
如果在查找过程中未找到目标值返回一个表示未找到的结果如 -1 或 None。
二分查找算法的时间复杂度是 O(log n)非常高效。
整数二分
二分的本质并不是一定要单调而是对一个区间可以化分成两个部分一部分一定满足条件另一部分一定不满足对于满足这种条件的我们可以找出两个边界点这样的话二分算法可以寻找这个性质的边界红色和黑色的边界都行因为是整数二分所以两边界不重合。
第一种情况二分左半部分
假如说有一串数字1233445688我们需要找到满足小于等于3的最大情况的子序列也就是我们需要找到最后一次出现的3我们可以如何做呢 我们让一个mid(lr1)/2 假如说a[mid]3,此时if(check(mid))true说明此时mid指向的值可能是答案但是我们无法保证其后面还有没有答案是3的所以此时应该是lmid,假如说此时a[mid]3,if(check(mid))false说明此时mid指向的是一定不满足条件的的那么此时应该是rmid-1。 我们继续不段重复以上操作直到lr时退出循环。
第二种情况(二分右半部分)
还是这个数字序列这次我们要找1233445688中第一次出现3的位置我们应该怎么做呢 我们还是让一个mid(lr)/2 假如说a[mid]3,此时if(check(mid))true说明此时mid指向的值可能是答案但是我们无法保证其前面还有没有答案是3的所以此时应该是rmid,假如说此时a[mid]3,if(check(mid))false说明此时mid指向的是一定不满足条件的的那么此时应该是lmid1。
注意第一种情况是lr1而不是lr为为什么呢
因为计算机的除法都是向下取整的所以就会出现问题假如说此时lr-1那么mid(lr)/2(ll1)/2l然后我们假如发现l还是满足条件的那么此时就会陷入lmid,midl的死循环
我们来写一道题
洛谷P2249 下面的代码是既有第一次出现也有最后一次出现的两种情况都写了。 代码如下
#include iostream
using namespace std;const int N 1e5 10; // 定义数组的最大容量数组a最多可以存放1e5个元素
int a[N], n, m; // 定义全局变量数组an为数组长度m为查询次数// check1函数用于检查a[mid]是否大于等于目标值x
bool check1(int mid, int x) {if (a[mid] x) {return true; // 如果a[mid]大于等于x返回true表示满足条件} else {return false; // 否则返回false表示不满足条件}
}// check2函数用于检查a[mid]是否小于等于目标值x
bool check2(int mid, int x) {if (a[mid] x) {return true; // 如果a[mid]小于等于x返回true表示满足条件} else {return false; // 否则返回false表示不满足条件}
}int main() {cin n m; // 输入数组的长度n和查询的次数mfor (int i 1; i n; i) {cin a[i]; // 依次输入数组a的元素}while (m--) { // 对每一次查询进行处理m次查询int x; // 定义要查询的目标值xcin x; // 输入目标值x// 首先进行二分查找寻找第一个大于等于x的位置int l 1, r n; // 初始化左右边界l是左边界r是右边界while (l r) { // 当左边界小于右边界时继续二分查找int mid (l r) 1; // 计算中间位置midif (check1(mid, x)) { // 如果a[mid]大于等于xr mid; // 缩小右边界至mid} else {l mid 1; // 否则缩小左边界至mid1}}// 查找完成后检查a[l]是否等于目标值xif (a[l] x) {cout l ; // 如果a[l]等于x输出位置l} else {cout -1 ; // 如果a[l]不等于x输出-1表示未找到}// 再进行一次二分查找寻找最后一个小于等于x的位置l 1, r n; // 重新初始化左右边界while (l r) {int mid (l r 1) 1; // 计算中间位置mid向上取整if (check2(mid, x)) { // 如果a[mid]小于等于xl mid; // 缩小左边界至mid} else {r mid - 1; // 否则缩小右边界至mid-1}}// 查找完成后再次检查a[l]是否等于目标值xif (a[l] x) {cout l ; // 如果a[l]等于x输出找到的最后位置l} else {cout -1 ; // 如果没找到输出-1}coutendl;}
}整数二分模板
bool check(int x) {// 这里是判断x是否满足某种性质的函数具体实现取决于实际问题// 可以根据x的值来返回true或false用于二分查找中的判断/* ... */
}// 区间[l, r]被划分为[l, mid]和[mid 1, r]时使用的二分查找
int bsearch_1(int l, int r) {// 二分查找的目的是在区间[l, r]中寻找满足某种性质的最小位置// l 是左边界r 是右边界最终返回满足性质的最小下标while (l r) { // 当左边界小于右边界时继续进行二分查找int mid (l r) 1; // 计算中间位置mid使用右移操作进行快速计算相当于 (l r) / 2if (check(mid)) { // 如果check(mid)为true表示mid满足性质r mid; // 将右边界缩小到mid因为我们要找满足性质的最小位置} else { // 否则mid不满足性质l mid 1; // 将左边界缩小到mid 1因为mid以及它左边的值都不满足条件}}return l; // 返回最终的左边界此时l r且为满足性质的最小位置
}// 区间[l, r]被划分为[l, mid - 1]和[mid, r]时使用的二分查找
int bsearch_2(int l, int r) {// 二分查找的目的是在区间[l, r]中寻找满足某种性质的最大位置// l 是左边界r 是右边界最终返回满足性质的最大下标while (l r) { // 当左边界小于右边界时继续进行二分查找int mid (l r 1) 1; // 计算中间位置mid并向上取整确保mid偏向右侧if (check(mid)) { // 如果check(mid)为true表示mid满足性质l mid; // 将左边界缩小到mid因为我们要找满足性质的最大位置} else { // 否则mid不满足性质r mid - 1; // 将右边界缩小到mid - 1因为mid以及它右边的值都不满足条件}}return l; // 返回最终的左边界此时l r且为满足性质的最大位置
}浮点数二分算法
浮点数二分相较于整数二分更加简单因为只有一个模板并且没有边界问题浮点数的二分查找可以用于求解需要精确值的问题例如求方程的解或几何问题中涉及浮点精度的求解。与整数二分查找不同浮点数二分查找必须考虑精度问题因为浮点数无法精确到某个具体值所以我们需要一个精度如 epsilon用于判断二分查找的终止条件。
假如说我们需要找一个数x的平方等于目标值2
代码如下
#include iostream
#include cmath // 包含abs函数用于计算绝对值
using namespace std;// 定义一个需要使用二分法求解的函数返回值为目标函数值
double f(double x) {// 举例寻找函数 f(x) x^2 - 2 的根return x * x - 2;
}int main() {double l 0, r 2; // 初始区间[l, r]假设根位于[0, 2]之间double eps 1e-7; // 定义精度eps即当结果误差小于1e-7时停止迭代// 当区间宽度大于精度要求时继续二分while (r - l eps) {double mid (l r) / 2; // 计算中间值if (f(mid) 0) { // 如果 f(mid) 0表示 mid 处的值在根的右侧r mid; // 缩小右边界至mid} else { // 否则 f(mid) 0表示 mid 处的值在根的左侧或是根l mid; // 缩小左边界至mid}}// 输出结果l 和 r 最终都会逼近根cout x ≈ l endl;cout 验证结果: f(x) f(l) endl; // 输出验证f(l)接近0
}浮点数二分模板
// 函数原型在浮点数区间 [l, r] 上使用二分查找找到满足某种性质的浮点数
double bsearch_3(double l, double r)
{const double eps 1e-6; // eps 是精度控制的参数当区间长度小于 eps 时停止二分查找// 1e-6 表示小数点后 6 位精度可根据题目要求调整精度// 当区间长度大于 eps 时继续进行二分查找while (r - l eps){// 计算区间的中点 middouble mid (l r) / 2;// 调用 check 函数判断 mid 是否满足给定的性质// 假设 check(mid) 返回 true则意味着 mid 及其右侧可能满足性质// 因此将右区间收缩到 mid继续在左侧区间 [l, mid] 上搜索if (check(mid)) r mid;// 否则mid 及其左侧不满足性质因此我们将左区间收缩到 mid继续在右侧区间 [mid, r] 上搜索else l mid;}// 最后返回左边界 l或右边界 r此时区间已经很小接近于精度要求的结果// 因为 l 和 r 的距离非常小最终答案应为 l 或 r 的近似值return l;
}整数二分算法和浮点数二分算法源代码
