题意

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

示例

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

思路

• 主要是利用二分查找，先查找对应的target的上界j，再查找其第一次出现的位置i,则j-i即为target出现的次数
• 需要注意的是，查找第一次出现的位置，可以通过查找target-1的上界来得到

代码

• cpp

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return upper_bound(nums.begin(),nums.end(),target) - lower_bound(nums.begin(),nums.end(),target);
    }
};

• java

class Solution {
    public int search(int[] nums, int target) {
        return helper(nums,target) - helper(nums,target-1);
    }

    int helper(int[] nums,int target){
        int i = 0;
        int j = nums.length - 1;
        while(i <= j){
            int m = (i+j)/2;
            if(nums[m] > target){
                j = m-1;
            }
            else{
                i = m+1;
            }
        }
        return i;
    }
}

总结

1. 对于查找时，要分target是否在数组中,若不在数组中，显然根据二分查找的算法规律，最后i为上界,j为下届,而若是target在数组中,则情况如下

   • 其中查找上界和下届主要是在原来二分查找时，在查找到等于target的地方进行修改，如果想查上界，就让i=m+1,人为的让相等的时候，不返回值，而是继续往右边查，这样查下去，最后必然使得i == j，而此时只需判断是大于target还是==target，两种情况操作完，都可使得i指向target的上界,而对于查找下届，让j=m-1即可
   • 查上届,i最后为上届,j为target最后出现的位置
   • 查下届,j最后为下届,i为target第一次出现的位置

2. 此题中涉及到了二分查询上界，其稍微改改即可查询下届以及对应的target，此查找模板极为重要,需要仔细记住