1. 题目描述
统计一个数字在排序数组中出现的次数。
2. 题目分析
- 题主一开始的方法：看见有序，使用二分，查找到target，向前向后分别遍历到不等于target的数字，因为数组中的target出现的次数是不确定的，所以，可能查找到n次，相当于O(n);
- 面试中，这种写法会被paas掉，所以我们需要用二分查找找到第一次出现target的下标，最后一次出现target的下标，
- 对于target出现的第一次下标,采用以下方式
当mid == 0的时候，也就是证明当前的数是从下标0开始的，则直接返回0(mid)
为了防止数组的越界，我们需要使当前的mid>0且array[mid-1]!=key
对于：right = mid - 1;我们可以理解成当前的key是位于中间的那一个，所以我们需要减少范围，也就是缩小right的值，让mid向前遍历。
if (array[mid] == key) { if ((mid == 0) || (mid > 0 && array[mid - 1] != key)) { return mid; } else { right = mid - 1; } }
- 对于target出现的最后一次下标，采取以下方式
当mid == array.lenth - 1的时候，也就是证明当前的数一直到最后。则直接返回mid
为了防止数组的越界，我们需要使当前的mid对于：i = mid + 1;我们可以理解成当前的key是位于中间的那一个，所以我们需要减少范围，也就是扩大left的值，让mid向后遍历。
if (array[mid] == key) { if (mid == array.length - 1 || mid < array.length - 1 && array[mid + 1] != key) { return mid; } else { left = mid + 1; } }
- 最后，我们返回（第二次出现的下标 - 第一次出现的下标 + 1）
3. 题目代码
class Solution { public int search(int[] nums, int target) { int num1 = erfenFirst(nums, 0, nums.length - 1, target); int num2 = erfenSecond(nums, 0, nums.length - 1, target); return num2 - num1 + 1; } public static int erfenFirst(int[] array, int left, int right, int key) { int mid = 0; while (left <= right) { mid = (left + right) / 2; if (array[mid] == key) { if ((mid == 0) || (mid > 0 && array[mid - 1] != key)) { return mid; } else { right = mid - 1; } } else if (array[mid] > key) { right = mid - 1; } else { left = mid + 1; } } return 1; } public static int erfenSecond(int[] array, int left, int right, int key) { int i = left; int j = right; while (i <= j) { int mid = (i + j) / 2; if (array[mid] == key) { if (mid == array.length - 1 || mid < array.length - 1 && array[mid + 1] != key) { System.out.println(mid); return mid; } else { i = mid + 1; } } else if (array[mid] > key) { j = mid - 1; } else { i = mid + 1; } } return 0; } }
