二分查找-变形3WA

常规
1 
#include<bits/stdc++.h>
using namespace std;
int n,a[100000];
int main()
{
  cin >> n;
  for(int i = 0;i < n;i++)
  {
    cin >> a[i];
  }
  int m;
  while(cin >> m)
  {
    int l = 0,r=n;
    bool tmp = 1;
    while(l+1<r)
    {
      int mid = (r-l)/2+l;
      if(a[mid]>m)
      {
        r=mid;
      }
      else if(a[mid]==m)
      {
        r=mid;
        tmp = 0;
      }
      else
      {
        l=mid;
      }
    }
    if(tmp)
    {
      cout << "0 ";
    }
    else
    {
      int l1=l;
      l = 0,r = n;
      while(l+1<r)
      {
        int mid = (r-l)/2+l;
        if(a[mid]>m)
        {
          r=mid;
        }
        else
        {
          l=mid;
        }
      }
      cout << (l-l1+1);
    }
  }
  return 0;
}
1 个赞
2

思路：
1.按照题目要求输入数据，存储到数组中去,
2.开始二分查找，二分查找进行下去的关键条件：l<=r
二分查找核心代码：

while(l<= r){
    mid=(l+r)/2;
    if (a[mid]<m){
        l=mid+1;
    }else{
        r=mid-1;
     }
}
找完之后记得判断是否有m，没有则直接输出0，有的话则在第一次二分查找结束后记录m出现左边界的位置p1
再通过第二次二分查找记录m出现右边界的位置p2
p2-p1即是m出现的个数
1 个赞
3

AC了记得给解决方案Thank you

1 个赞
4

此帖子已被社区举报，现已被临时隐藏。

1 个赞
5

不能直接发AC代码哦

1 个赞