福州工程网站建设团队北京网站建设制作开发

剑指 Offer 53 - I. 在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。

示例 1:

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

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

提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

解法一：
我觉得难点不是想到用二分法（题目中指明给定有序数组就是明显地暗示：可以使用二分法）；
而是如何设计二分法……这个我还在学习，比如while循环条件要不要等号，循环内部left是等于mid，还是mid+1，等等；
我日后来补补二分法专项……

  public int search(int[] nums, int target){if(nums==null || nums.length==0) return 0;int first = rightBound(nums,target-1);// the index where target firstly appearsint last = rightBound(nums,target);// the index after the last targetreturn last-first;}public int rightBound(int[] nums,int target){// 返回第一个大于target的元素的位置int i=0,j=nums.length-1;while(i<=j){int mid = (i+j)/2;if(nums[mid]<=target) i=mid+1;else j=mid-1; }return i;}

第二种解法
首先，沿用解法一：首先找到“=target区”的右边界（开的，表示这个边界所指的元素不是target）；
然后，遍历着数有多少相同的元素。

 public int search(int[] nums, int target){int l=0,r=nums.length-1;int mid=0;while(l<=r){mid = (r+l)/2;if(nums[mid]<=target) l=mid+1;else r = mid-1;}// l is the open right boundl-=1;int count=0;while(l>=0 && nums[l]==target){l--;count++;}return count;}