day98(9.8)

1. 在排序数组中查找数字 I

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

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

思路：

• 要点： 已经完成排序
• 那么所有的目标值都是连续的
• 可以用常见的高效的查找算法确定一个值的位置（这里使用二分查找算法）

• 然后两边进行探索，判断目标值，直到扫描到第一个非目标值停止

  class Solution {
    public int search(int[] nums, int target) {
        // 二分法找到目标数, 然后左右探索统计数目
        int n = binarySearch(0,nums.length-1,nums,target);
        if(n==-1){
            return 0;
        }
        int count = 1;
        int temp1 = n-1;
        int temp2 = n+1;
        while(temp1>=0 && nums[temp1]==target){
            count++;
            temp1--;
        }
        while(temp2<nums.length && nums[temp2]==target){
            count++;
            temp2++;
        }
        return count;
    }
  
    public int binarySearch(int left,int right,int[]nums,int target){
        if(left>right){
            return -1;
        }
        int mid = (left+right)/2;
        int midVal = nums[mid];
        if(midVal==target){
            return mid;
        }else if(midVal<target){
            return binarySearch(mid+1,right,nums,target);
        }else{
            return binarySearch(left,mid-1,nums,target);
        }
    }
  }