原创博文，转载请注明出处！

# 题目

# 思路

      利用二分查找法，查找元素k在排序数组中第一次出现的位置m及最后一次出现的位置n，m-n+1即为元素k再排序数组中出现的次数。

      二分查找法在数组中找到第一个k的思路：先拿数组中间元素mid和查找元素k比较，如果k<mid，则第一个k只可能出现在数组的前半段；如果k>mid，则第一个k只可能出现在数组的后半段；如果k=mid，则先判断中间元素是不是第一个k（如果mid前的元素不是k，则中间元素是第一个k；如果mid前的元素是k，则第一个k出现在数组的前半段。

      二分查找法在数组中找到最后一个k的思路：先拿数组中间元素mid和查找元素k比较，如果k<mid，则最后一个元素k只可能出现在数组的前半段；如果k>mid，则最后一个元素k只可能出现在数组的后半段；如果k=mid，则先判断中间元素是不是最后一个k（如果mid后的元素不是k，则中间元素是最后一个k；如果mid后的元素是k，则最后一个k出现在数组的后半段。

# 代码

1 #include 
     
        2 #include 
      
         3 using namespace std;  4   5 class Solution {  6 public:  7     // 查找元素k在有序数组中出现的次数  8     int GetNumberOfK(vector
       
         data ,int k)  9     { 10         // 特殊输入 11         if(data.size() == 0) 12             return 0; 13         cout<
        
         <
         

data,int k,int l,int r) 33 { 34 // 递归出口 35 if(l>r) 36 return -1; 37 38 int mid = (l+r)>>1; 39 40 if(k

data[mid]) 45 { 46 l = mid+1; 47 } 48 else 49 { 50 if((mid>0 && data[mid-1] != k) || mid == 0) 51 return mid; 52 else 53 r = mid-1; 54 } 55 return GetFirstK(data,k,l,r); 56 } 57 58 // 二分查找法，查找最后一个k的位置 59 int GetLastK(vector

data,int k,int l,int r) 60 { 61 if(l>r) 62 return -1; 63 64 int mid = (l+r)>>1; 65 66 if(k

data[mid]) 69 l = mid+1; 70 else 71 { 72 if((mid < data.size()-1 && data[mid+1]!=k) || mid == data.size()-1) 73 return mid; 74 else 75 l = mid+1; 76 } 77 return GetLastK(data,k,l,r); 78 } 79 }; 80 int main() 81 { 82 cout << "二分查找法计算数字k在排序数组中出现的次数" << endl; 83 // 空数组 84 vector

arr1; 85 // 数组中不包含查找的数字 86 vector

arr2 = {1,3,5,7,9,10}; 87 // 数组中包含查找的数组（出现一次） 88 vector

arr3 = {1,2,2,2,2,3,3,3,4,5}; 89 // 数组中包含查找的数组（出现多次） 90 vector

arr4 = {1,2,3,4,4,4,7,8,9,10}; 91 Solution solution; 92 cout<

<