欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二分查找--数字在排序数组中出现的次数

程序员文章站 2022-03-14 23:50:56
...

统计一个数字在排序数组中出现的次数。

看到有序数组,第一反应就应该是二分查找,复杂度为O(logn),比从头到尾扫描复杂度O(n)效率高。分别用二分查找法第一次和最后一次出现的数字的下标,相减即可、

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
      int number=0;
         int a=Getfirstnumber( data ,0,data.size()-1,k);
     int b=Getlastnumber(data ,0,data.size()-1,k);
      if(a>-1&&b>-1)
           number=b-a+1;
        return number;
    }
    int Getfirstnumber(vector<int> data ,int start,int end,int k) {
       if(start>end)
           return -1;
        int middle =(start+end)/2;
        if( data[middle]==k)
        {
            if(middle==start||( middle-1>=start&&data[middle-1]!=k))
             
                return middle;
            else
                end= middle-1;
        }
        else if(data[middle]>k)
        {end=middle-1;
            
        }
         else
         start=middle+1;
            
       
       return Getfirstnumber(data ,start,end,k);                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  
        
    }
    int Getlastnumber(vector<int> data ,int start,int end,int k) {
       if(start>end)
           return -1;
        int middle =(start+end)/2;
        if( data[middle]==k)
        {
           
              if((middle+1<=end&&data[middle+1]!=k)||middle==end)
            return middle;
            else
               start=middle+1;
        }
        else if(data[middle]>k)
        {end=middle-1;
            
        }
         else
         { start=middle+1;
            
        }
      return Getlastnumber(data ,start, end,k);     
    }
};

注意:边界条件。

若是使用STL :

 int GetNumberOfK(vector<int> data ,int k) {
      return count(data.begin(),data.end(),k);
    }注意count()是顺序查找,复杂度o(n)
auto p1 = lower_bound(data.begin(), data.end(), k);
 auto p2 = upper_bound(data.begin(), data.end(), k);
 return p2 - p1;


upper_bound(i) 返回的是键值为i的元素可以插入的最后一个位置(上界) 
lowe_bound(i) 返回的是键值为i的元素可以插入的位置的第一个位置(下界)。

为二分查找。当容器中没有要查找的元素时,返回值是一样的。