Contest1150 - 【C3】二分查找-第一节课
2023-07-26 09:00:00
3333-07-26 13:00:00
信息与公告
#include<bits/stdc++.h> using namespace std; int n,m,a[1000001]; //存在时 返回的下标:最左边的x的下标 //不存在时 返回的是第一个大于x的下标 //返回第一个>=x的位置 可能越界 想象右侧有无穷大的边界 int findLeft(int x){ int L=1,R=n; while(L<=R){ int mid=(L+R)/2; if(x<=a[mid]){//相等 往左找 R=mid-1; }else{ L=mid+1; } } return L;//返回L } //返回最后一个<=x的 R 最左边有无穷小的边界 int findRight(int x){ int L=1,R=n; while(L<=R){ int mid=(L+R)/2; if(x<a[mid]){ R=mid-1; }else{ L=mid+1;//相等 往右找 } } return R;//返回R } int main(){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } cin>>m;//要查找的次数 while(m--){ int x; cin>>x; int L=findLeft(x); int R=findRight(x); cout<<"findLeft 返回的L:"<<L<<endl; cout<<"findRight 返回的R:"<<R<<endl; } return 0; } //(L+R)/2 左:R=mid-1; 右:L=mid+1; //6 //1 2 2 3 3 3