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

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

  1. 示例 1:
  3. 输入: nums = [5,7,7,8,8,10], target = 8
  4. 输出: 2
  5. 示例 2:
  7. 输入: nums = [5,7,7,8,8,10], target = 6
  8. 输出: 0
  10. 限制：
  12. 0 <= 数组长度 <= 50000

思路:

  • 数组是有序数组，则不需要进行整体遍历计数。

  • 这里对二分查找进行修改，从而满足题目的要求。

    • 通过二分查找，传递count计数器，并且返回值就是该count，来通过递归进行计数。
    • 首先找到数组中的对应值。
      • 这里可以对二分查找进行优化，改进成斐波拉契查找、插值查找，以提高第一次的锁定target的效率。

    • 然后分别向左、向右循环判断是否有其他等于target的数，进行记录。

      class Solution {
public int search(int[] nums, int target) {
   if(nums.length==0){
       return 0;
   }
   int count = 0;
   return midSearch(nums,0,nums.length-1,target,count);
}

// 二分查找
public int midSearch(int[] arr,int left,int right,int target,int count){
   int mid = (left+right)/2;
   int midValue = arr[mid];
   if(midValue == target){
       count++;
       int leftSearch = mid-1;
       int rightSearch = mid+1;
       while(leftSearch>=0&&arr[leftSearch]==target){
           count++;
           leftSearch-=1;
       }
       while(rightSearch<arr.length&&arr[rightSearch]==target){
           count++;
           rightSearch+=1;
       }
       return count;
   }else if(target<midValue&&mid-1>=left){
       return midSearch(arr,left,mid-1,target,count);
   }else if(target>midValue&&mid+1<=right){
       return midSearch(arr,mid+1,right,target,count);
   }
   return count;
}
}