数字在升序数组中出现的次数

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

解题思路

有序数组一定要想到二分查找！有序数组一定要想到二分查找！有序数组一定要想到二分查找！

因为有序，所以目标值如果有多个，肯定是连在一起。又已知我们可以在有序数组中查找任意一个值，因此我们可以先查找目标范围的下界和上界。

上界定义为：指向最后一个目标值。

下界定义为：指向第一个目标值。

public class Solution { public int GetNumberOfK(int[] array , int k) { if(array == null || array.length == 0) { return 0; } int firstK = getFirstKey(array, k, 0, array.length - 1); int lastK = getLastKey(array, k, 0, array.length - 1); if(firstK != -1 && lastK != -1) { return lastK - firstK + 1; } return 0; } // 递归写法 public int getFirstKey(int[] array, int k, int start, int end) { if(start > end) { return -1; } int mid = (start + end) >> 1; if(array[mid] > k) { return getFirstKey(array, k, start, mid - 1); } else if(array[mid] < k) { return getFirstKey(array, k, mid + 1, end); } else if(mid - 1 >= 0 && array[mid - 1] == k) { return getFirstKey(array, k, start, mid - 1); } else { return mid; } } // 循环写法 public int getLastKey(int[] array, int k, int start, int end) { int len = array.length; int mid = (start + end) >> 1; while(start <= end) { if(array[mid] > k) { end = mid - 1; } else if(array[mid] < k) { start = mid + 1; } else if(mid + 1 < len && array[mid + 1] == k) { start = mid + 1; } else { return mid; } mid = (start + end) >> 1; } return -1; } }