AKSZ-二分算法
2024-03-31 17:33:58
发布于:广东
二分查找
模板
#include<bits/stdc++.h>
using namespace std;
int x,n,a[105],ans=-1;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
cin>>x;
int l=1,r=n;//二分的上下边界
//在[l,r]闭区间包l,r //开区间[l,r)包l不包r
while(l<=r){//例题
int mid=(l+r)>>1;
if(a[mid]==x){
ans=mid;//表示找到了
break;
}
else if(a[mid]>x){
r=mid-1;
}
else{
l=mid+1;
}
}
return 0;
}
1.查找的数字是有序的,没有顺序的
升序数组 &
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[]={1,1,2,4,4,6,7,8};
int b=4,n=8;
int id=lower_bound(a,a+n,x)-a;//6
cout<<id<<endl;
int id=upper_bound(a,a+n,b)-a;//5
cout<<id<<endl;
return 0;
}
适用于升序函数 lower_bound();
-数组第个下标开头;
返回值 是第个大于等于 审查元素 的下标
适用于升序函数 upper_bound();
-数组第个下标开头;
返回值 是第个大于 审查元素 的下标
反码
正数的反码:与原码相同
负数的反码:在原码的基础上,除符号位外取反,0变1,1变0
这里空空如也
有帮助,赞一个