一，问题描述
假设给定一个有序的整型数组arr，以及一个整数 k，问 k在数组中出现了几次？
二，求解思路
①数组是有序的，故可考虑用二分查找
②如果能找到 k 在数组中第一次出现时的索引位置first_index 和 最后一次出现时的索引位置last_index
就可以知道 k 出现的次数了: (last_index - first_index) + 1
而对于有序数组而言，可以通过二分查找求出某个数第一次出现的索引位置 和 最后一次出现的索引位置。故总的时间复杂度为O(logN)
③特殊情况考虑
k 不在数组中时怎么办？ 数组arr为null 或者 数组 arr.length == 0
核心思路：求解 k 第一次出现时的索引位置
首先找出arr[middle]，如果 k 比中间元素大，则在右边寻找k第一次出现时的索引位置（递归），若 k 比中间元素小，则在左边寻找...（递归）。
若 k == arr[middle]，则需要判断 arr[middle -1] 是否等于 k，若不等于k，则说明 middle 就是 k 第一次出现时的索引；若等于 k，则继续递归在左边寻找，但是此时要注意 左边索引不要越界（middle == low 了，就不能再往左边寻找了）。
同理可求解，k 最后一次出现时的索引位置。
三，完整代码实现
public class OccFreq { /** * 求解 k 在 arr 中第一次出现的索引位置 * @param arr 有序数组 * @param k * @return k第一次出现的索引位置,若 k 不在 arr中返回 -1 */ public static int getFirst(int[] arr, int k){ if(arr == null || arr.length == 0) throw new IllegalArgumentException("arr == null or arr.lenght == 0"); return getFirst(arr, 0, arr.length - 1, k); } private static int getFirst(int[] arr, int low, int high, int k){ int middle = (low + high) / 2; if(middle == low || middle == high) { if(arr[middle] == k) return middle; else // throw new IllegalArgumentException(k + " not in arr"); return -1; } if(arr[middle] > k) return getFirst(arr, low, middle - 1, k); else if(arr[middle] < k) return getFirst(arr, middle + 1, high, k); else { if(arr[middle - 1] == k) return getFirst(arr, low, middle - 1, k); else return middle; } } /** * 求解 k 在 arr 中最后一次出现的索引 * @param arr * @param k * @return k 在arr中的最后出现的索引, 若 k 不在 arr中返回 -1 */ public static int getLast(int[] arr, int k){ if(arr == null || arr.length == 0) throw new IllegalArgumentException("arr == null"); return getLast(arr, 0, arr.length - 1, k); } private static int getLast(int[] arr, int low, int high, int k){ int middle = (low + high) / 2; //已经寻找到最左边 或 最右边了. if(middle == low || middle == high) { if(arr[middle] == k) return middle; else // throw new IllegalArgumentException(k + " not in arr"); return -1;//k 不在 arr中 } if(arr[middle] > k){//继续在左边寻找 return getLast(arr, low, middle - 1, k); } else if(arr[middle] < k){//继续在右边寻找 return getLast(arr, middle + 1, high, k); } else//k== arr[middle] { if(arr[middle + 1] == k) return getLast(arr, middle + 1, high, k);//继续在右边寻找 else return middle; } } /** * 求解 k 在 arr数组中出现的次数 * @param arr 有序数组 * @param k * @return k 在 arr 数组中出现的次数 */ public static int freq(int[] arr, int k){ int first_index = getFirst(arr, k); int last_index = getLast(arr, k); if(first_index < 0 && last_index < 0) return 0; return last_index - first_index + 1; } public static void main(String[] args) { int[] arr = {2,4,5,6,8,8,8,9}; int freqs = freq(arr, 1); System.out.println(freqs); } }
本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/p/5674810.html，如需转载请自行联系原作者
