数的范围（二分）

给定一个按照升序排列的长度为n的整数数组，以及q个查询。
对于每个查询，返回一个元素k的起始位置和终止位置（位置从О开始计数)。
如果数组中不存在该元素，则返回-1 -1。
输入格式
第一行包含整数n和q，表示数组长度和询问个数。
第二行包含n个整数(均在1～10000范围内)，表示完整数组。
接下来q行，每行包含一个整数k，表示一个询问元素。
输出格式
共q行，每行包含两个整数，表示所求元素的起始位置和终止位置。
如果数组中不存在该元素，则返回-1 -1。

输入样例：

  

   

    

     

    
    

     

      6 3
     
    
   

    

     

    
    

     

      1 2 2 3 3 4
     
    
   

    

     

    
    

     

      3
     
    
   

    

     

    
    

     

      4
     
    
   

    

     

    
    

     

      5
     
    
  
 

输出样例：

  

   

    

     

    
    

     

      3 4
     
    
   

    

     

    
    

     

      5 5
     
    
   

    

     

    
    

     

      -1 -1
     
    
  
 

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int N = 100010;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int n, m;
     
    
   

    

     

    
    

     

      int q[N];
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          scanf("%d%d", &n, &m);
     
    
   

    

     

    
    

     
    for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    while (m -- )
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        int x;
     
    
   

    

     

    
    

     

              scanf("%d", &x);
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        int l = 0, r = n - 1;
     
    
   

    

     

    
    

     
        while (l < r)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            int mid = l + r >> 1;
     
    
   

    

     

    
    

     
            if (q[mid] >= x) r = mid;
     
    
   

    

     

    
    

     
            else l = mid + 1;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
        if (q[l] != x) cout << "-1 -1" << endl;
     
    
   

    

     

    
    

     
        else
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  cout << l << ' ';
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
            int l = 0, r = n - 1;
     
    
   

    

     

    
    

     
            while (l < r)
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                int mid = l + r + 1 >> 1;
     
    
   

    

     

    
    

     
                if (q[mid] <= x) l = mid;
     
    
   

    

     

    
    

     
                else r = mid - 1;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

                  cout << l << endl;
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

一招教你搞定二分：mid=l+r>>1之后看有机会l+r+1根据实际情况，一般先弄几个简单数据手动模拟一番，看会不会出现死循环，总之灵活为上！奥利给！

这个题要找到双重边界，那么就要二次二分。

文章来源: blog.csdn.net，作者：irrationality，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_54227557/article/details/120594703