本文共 2723 字，大约阅读时间需要 9 分钟。

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

思路：已知数组是排好序的，对于一个有序的数组，方法1：要判断一个数字k在数组中出现的次数一个直接的方法是顺序遍历，记录k的出现次数，时间复杂度为O(n)，显然不是最优；方法2：也可以使用二分法先找到这个k值，时间复杂度是O(logn)，但是这时找到的k可能是多个k中的其中一个，不知道k的开始位置和结束位置再哪里，需要从k开始向左和向右遍历找出第一个k和最后一个k，这也是遍历，在最坏情况下当整个数组全部都是k值时，时间复杂度为O(n)，就算不是最坏情况，也需要遍历部分数组，因此时间复杂度也是O(n)级别的。显然也不是最优。方法3：使用改进后的二分法找出第一个k和最后一个k。二分法的作用是在排序的数组中找出指定的一个数，通过不断与中间值比较、对半分割将查找范围缩小一半从而保证时间复杂的为O(logn)，过去的二分法中，得到a[middle]值之后，将k与a[middle]进行比较，如果k< a[middle]则在左边，更换边界条件继续查找；如果k> a[middle]则在右边，更换查找边界继续查找；如果k== a[middle]则表示找到，直接结束；现在，当k== a[middle]时还不能结束，要判断a[middle-1]是否等于k,如果不等，表示这个k值是第一个k，记录这个下标作为firstK=middle；否则说明这个k不是第一个k，第一个k还在前面的部分中，于是调整查找边界条件，继续使用二分法进行查找；使用相同的方法可以找到lastK；这里可是使用while循环或者递归来实现（而且是为递归，很简单），结束循环调用的边界条件是找到firstK而return或者都边界了还是找不到（这里又两种处理方法对应不同的边界，如果每次二分判断时，当k>middle时，令新的left=middle+1，当k<middle时令right=middle-1，此时循环中止的条件是right<left，即要当两个指针错位时才表示循环结束；如果当k>middle时，令新的left=middle，当k<middle时令right=middle，那么循环终止条件是right-left<=1；过去我使用第二种，现在统一改为第一种）

特殊的，注意：在二分法每次判断后调整查找边界时，left=middle+1;right=middle-1;不会导致数组越界；但是本题中，附加的判断array[middle-1]!=k；array[middle+1]!=k中middle-1和middle+1可能导致数组越界，因此必须修复，当middle-1和middle+1越界时，说明当前middle是数组的第一个或者最后一个元素，那么显然是重复数字k的第一个k和最后一个k，直接返回middle作为下标即可。

//改进二分法的判断条件，使得找到第一个或者最后一个k时才停止二分寻找，保证整体的复杂度为O(logn)public class Solution {    public int GetNumberOfK(int [] array , int k) {        int firstKIndex=this.getFirstKIndex(array,0,array.length-1,k);        int lastKIndex=this.getLastKIndex(array,0,array.length-1,k);        //可能k不存在        if(firstKIndex==-1||lastKIndex==-1) return 0;        return lastKIndex-firstKIndex+1;   }        //该方法用来递归查找第一个k,如果没有k则返回-1     public int getFirstKIndex(int [] array , int left, int right, int k) {        //使用递归或者while循环来实现        int middle=(left+right)/2;        //递归的终止条件,表示找不到这个数，即出现次数为0        if(left>right) return -1;        if(k
   
    array[middle]){            //k在右边，调整查找区间在右边查找            left=middle+1;        }else{            //k等于middle，看这个k是否是第一个k            if(middle-1<0||array[middle-1]!=k) return middle;   //千万注意middle的越界可能            //如果不是第一个，则继续在前面二分查找            right=middle-1;        }        return getFirstKIndex(array,left,right,k);   }         //该方法用来递归查找最后一个k,如果没有k则返回-1     public int getLastKIndex(int [] array , int left, int right, int k) {        //使用递归或者while循环来实现        int middle=(left+right)/2;        //递归的终止条件,表示找不到这个数，即出现次数为0        if(left>right) return -1;        if(k
    
     array[middle]){            //k在右边，调整查找区间在右边查找            left=middle+1;        }else{            //k等于middle，看这个k是否是最后一个k            if(middle+1>array.length-1||array[middle+1]!=k) return middle; //千万注意middle+1越界的可能            //如果不是第一个，则继续在前面二分查找            left=middle+1;        }        return getLastKIndex(array,left,right,k);   }}
    
   

转载地址：http://gvzin.baihongyu.com/