统计目标成绩的出现次数（数字在排序数组中出现次数），剑指offer,力扣

这里分享一个取中点的小知识：

   假设 low与high分别在数组左右两边，则中点=low+(high-low)

（这种写法看起来有点脱裤子放屁的意思，但)它主要好处是防止（high+low）过大时造成溢出

代码：

class Solution {
    public int countTarget(int[] scores, int target) {
        // 搜索右边界 right
        int i = 0, j = scores.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(scores[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;
        // 若数组中无 target ，则提前返回
        if(j >= 0 && scores[j] != target) return 0;
        // 搜索左边界 right
        i = 0; j = scores.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(scores[m] < target) i = m + 1;
            else j = m - 1;
        }
        int left = j;
        return right - left - 1;
    }
}
 

优化：

由于上面出现了两次二分查找，我们可以提高代码的复用性，将查找右边界right封装在一个函数中，而target 是整数，所以利用target 与target-1的下标之差

代码：

class Solution {
    public int countTarget(int[] scores, int target) {
        return helper(scores, target) - helper(scores, target - 1);
    }
    int helper(int[] scores, int tar) {
        int i = 0, j = scores.length - 1;
        while(i <= j) {
            int m = i+(j-i) / 2;
            if(scores[m] <= tar) i = m + 1;
            else j = m - 1;
        }
        return i;
    }
}

 评论区大佬的注释：

1、 while(i <= j)，这里不可用是i < j ，设想int[] nums = {1,2,3}，target=3，第一次i = 0，j = 2；第二次 i = 1，j = 2；第三次 i = 2，j = 2。如果是while(i < j)，而第三次是i = j ，不满足 i < j 的条件，退出while循环，会导致无法判断 i = j 的情况，不知道nums[i]是否等于target，就直接返回。

2、第一个if语句： if(nums[m] <= tar) ，这里因为合并了nums[m] < tar和nums[m] = tar两种情况，所以一开始看的十分头晕，建议为了可读性还是分开写。主要说 nums[m] = tar，因为helper方法是求右边界的！所以只要nums[m] = tar，则 i = m + 1，直到nums[m] 不等于 tar，此时就找到了tar的右边界。所以只要返回（tar的右边界减去tar-1的右边界），即可得到tar出现的次数。(这也说明为什么nums[m] = tar时，还需要 i = m +1，因为这是为了【找右边界】，与二分查找略有不同，二分查找是nums[m] = tar，就返回m了）

3、假如tar-1不存在呢？比如{1,2,3,5,7,7,7,8}，tar=7，而tar-1=6并不在数组nums里边。回看第二个问题if(nums[m] <= tar)合并了两个条件， 上边说了nums[m] = tar，这里说说nums[m] < tar。其实tar-1存在与否并不重要，按照开头的数组，设tar=6。第一次i = 0，j = 7，m=3，nums[m]=5 tar；第三次i = 4，j = 4，m = 4，nums[m] = 7 >tar；第四次 i = 4，j = 3，i>j 退出while，renturn 4，tar的右边界为下标4。为什么tar不存在不影响？我展示一下拙见，如有合适的解释，欢迎大佬补充。因为helper方法是为了求右边界，tar不存在时，不考虑nums[m] == tar的判断；nums[m] > tar，j = m-1；nums[m] < tar，i = m+1，最终返回的是tar的右边界（return i 保证是返回右边界，不可用return j）。所以tar的右边界一定存在，即使tar不存在

直接一次二分查找：

（不过在某些极端情况会出现时间复杂度退化）

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low<=high){
            //防止整数过大而溢出
            int mid=low+(high-low)/2;
            if(nums[mid]<target){
                low=mid+1;
            }else if(nums[mid]>target){
                high=mid-1;
            }else{
                if(nums[high]!=target)
                    high--;
                else if(nums[low]!=target)
                    low++;
                else
                    break;
            }
        }
                   //返回的要+1，因为是从数组下标开始
        return high-low+1;
    }
}