AKSZ-二分算法
2024-03-31 17:32:22
发布于:广东
二分查找
二分板子
#include<bits/stdc++.h>
using namespace std;
int n,x,mid;
int a[105];
bool check(int mid){
return a[mid]>=x;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);//关闭同步流
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int x;cin>>x;
int l=1,r=n;//二分的上下边界
int ans=-1;
//在 [l,r] 闭区间//开区间[l,r)不包括最后一个节点
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){//check条件
ans=mid;//找到了
r=mid-1;
}else{
l=mid+1;
}
}
cout<<ans;
return 0;
}
lower_bound()函数(找不到返回n+1)
lower_bownd(数组开头下表,数组结尾下表+1,待查元素)-数组第零个下标开头
返回值为 第一个大于等于 待查元素的下标
upper_bound()函数(找不到返回n+1)
upper_bownd(数组开头下表,数组结尾下表+1,待查元素)-数组第零个下标开头
返回值为 第一个大于 待查元素的下标
小数二分
#include<bits/stdc++.h>
using namespace std;
double n,x;
bool check(int mid){
return mid*mid<=n;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);//关闭同步流
cin>>n;
int x;cin>>x;
double l=0.0,r=n;//二分的上下边界
//在 [l,r] 闭区间//开区间[l,r)不包括最后一个节点
double ans=-1;
double eps = 1e-6;//精度控制 10^-6
while(r-1>=eps){
double mid=(l+r)/2.0;
if(check(mid)){//check条件
ans=mid;//找到了
r=mid;
}else{
r=mid;
}
}
cout<<ans;
return 0;
}
补码
在反码上+1
正数反码:与源码相同
负数补码:在原码基础上,除符号位外取反
这里空空如也
有帮助,赞一个