题解 P1918 【保龄球】

· · 题解

虽然这道题目有很多方法可以过，但是最好练一下二分查找， 这里讲一下c++二分查找的思路：

重点是函数部分，先定义查询的左右区间为1到n,然后开始二分，如果我们要找的值比这个中间值位置的数组小，那就去左侧的区间找，否则去右侧，没有的话返回0。

具体实现看代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100001
using namespace std;
int n,t,x,a[maxn];
struct node {                 //id为位置，a为球的数量。
    int id,a;
}e[maxn];
inline int find(int x) {       //二分查找，上面讲的很清楚了。
  int l=1,r=n;
  while(l<=r) {
    int mid=(l+r)>>1;
    if(e[mid].a==x) return mid;
    if(e[mid].a>x) r=mid-1;
    else l=mid+1;
  }
  return 0;
}
inline bool cmp(node x,node y) {   //二分查找必须有单调性，所以先从小到大排一边序。
  return x.a<y.a;
}
int main() {
  scanf("%d",&n);
  for(int i=1;i<=n;++i) scanf("%d",&e[i].a),e[i].id=i;
  sort(e+1,e+1+n,cmp);
  scanf("%d",&t);
  while(t--) {
    scanf("%d",&x);
    cout<<e[find(x)].id<<'\n';        //查完了就直接输出位置就行了。
  }
  return 0;
}

这篇题解只针对于想学习二分查找的同学，有什么不懂的可以私信找我！！！