2021-09-29

public class Solution {
    public static void main(String[] args) {
        int[]a = {1,2,3,4,5,7,7,7,7,7,7,7,7,8,9,10};
        Solution solution = new Solution();

        //开始位置目标数的索引
        int firstIdx = solution.findBeginPostion(a,7);
        //结束位置目标数的索引
        int lastIdx = solution.findOverPostion(a,7);

        if (firstIdx == -1 && lastIdx == -1) System.out.println("没有目标值");

        int x = lastIdx - firstIdx + 1;
        System.out.println("目标数个数为" + x);

    }

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

        //循环进行 二分查找 ，直到左端点位置超过右端点
        //或者在循环过程中找到了起始位置
        while (left <= right){
            int mid = (left + right)/2;
            if (nums[mid] == target){
                if (mid == 0 || target > nums[mid-1]){
                    return mid;
                }
                right = mid-1;
            }else if (nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid-1;
            }
        }
        return -1;
    }

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

        while (left <= right){
            int mid = (left + right)/2;
            if (nums[mid] == target){
                if (mid == nums.length-1 || target < nums[mid+1]){
                    return mid;
                }
                left = mid + 1;
            }else if (nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return -1;
    }
}