【二分查找】LCR 172. 统计目标成绩的出现次数

LCR 172. 统计目标成绩的出现次数

解题思路

• 二分查找
• 计算Target的左边界 计算右边界
• 右边界 - 左边界 + 1

class Solution {
   
    public int countTarget(int[] scores, int target) {
   
        // 计算target的左边界 还有右边界

        if(right_bound(scores,target) == -1){
   
            return 0;
        }

        return right_bound(scores,target) - left_bound(scores,target) + 1;
    }

    int left_bound(int[] nums,int target){
   
        int left = 0;
        int right= nums.length - 1;

        while(left <= right){
   
            int mid = (right - left)  / 2 + left;

            if(nums[mid] < target){
   
                left = mid + 1;
            }else if(nums[mid] > target){
   
                right = mid - 1;
            }else if(nums[mid] == target){
   
                // 缩小右边界
                right = mid - 1;
            }
        }

        if(left >= nums.length ||nums[left] != target){
   
            return -1;
        }

        return left;

    }


int right_bound(int[] nums,int target){
   
        int left = 0;
        int right= nums.length - 1;

        while(left <= right){
   
            int mid = (right - left)  / 2 + left;

            if(nums[mid] < target){
   
                left = mid + 1;
            }else if(nums[mid] > target){
   
                right = mid - 1;
            }else if(nums[mid] == target){
   
                // 缩小左边界
                left = mid + 1;
            }
        }

        if(right < 0 ||nums[right] != target){
   
            return -1;
        }

        return right;

    }

    
}