題目來源-洛谷網

參考代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int m,n,a[N],b;
int find(int t)
{int l=1,r=n;while(l<r){int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) r=mid;//中間值比查找的值大或者相等，區間左移 else l=mid+1; }if(a[l]==t) return r;  //此時 l=r 都是要求的值 else return -1;
}
int main()
{int ans;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>b;ans=find(b);cout<<ans<<" ";}return 0;
}

如果要求的是輸出編號的最大值
參考代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int m,n,a[N],b;
int ans; 
int find(int t)
{int l=1,r=n;while(l<r){int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]<=t) l=mid+1;//中間值比查找的值大或者相等，區間左移 else r=mid; }if(a[l-1]==t) return l-1;  //區間在右移 ，右端的值不會滿足條件 else return -1;
}
int main()
{int ans;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>b;ans=find(b);cout<<ans<<" ";}return 0;
}

萬能公式套用版

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int m,n,a[N],b;
int ans; 
int find(int t)
{int l=1,r=n;while(l<=r) //再求最小編號時，l r相鄰 比如 133 一定要注意最小編號是否能拿到 {int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) {ans = mid; //記錄值 r=mid-1; }else l=mid+1;}if(a[ans]==t) return ans;  else return -1;
}
int main()
{int ans;cin>>n>>m;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>b;ans=find(b);cout<<ans<<" ";}return 0;
}

二分標準模板

int find(int t)
{int l=1,r=n;while(l<=r) //一定是相等{int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) {ans = mid; //記錄值 r=mid-1; }else l=mid+1;}if(a[ans]==t) return ans;  else return -1;
}

求較小編號

int find(int t)
{int l=1,r=n;while(l<r) {int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]>=t) {r=mid; }else l=mid+1;}if(a[r]==t) return r;  //l也對else return -1;
}

求較大編號

int find(int t)
{int l=1,r=n;while(l<r) {int mid=(l+r)/2;//防止溢出 mid = l + (r-l) /2 ;if(a[mid]<=t) {l=mid+1;}else r=mid; }if(a[l-1]==t) return l-1;  //l會比準確值大些else return -1;
}