题目描述

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

 

思路：看到排序数组，首先考虑二分查找。我们找到数字在排序数组中最先出现和最后出现的下标，即得到次数。

1 class Solution { 2 public: 3     int GetNumberOfK(vector
     
       data ,int k) { 4         int len = data.size(); 5         int left = 0, right = len - 1, l, r; 6         int mid; 7         // 先找最左边的index，如果data[mid] == k,我们也将right = mid - 1, 8         // 因为我们只要最左边的index，下面找最右边的index也是同理。 9         while (left <= right) {10             mid = (right - left) / 2 + left;11             if (data[mid] >= k) {12                 right = mid - 1;13             } else {14                 left = mid + 1;15             }16         }17         l = left;18         right = len - 1;19         while (left <= right) {20             mid = (right - left) / 2 + left;21             if (data[mid] <= k) {22                 left = mid + 1;23             } else {24                 right = mid - 1;25             } 26         }27         r = right;28         return (r - l + 1);29     }30 };