《剑指offer》面试题53：在排序数组中查找数字

题目：数字在排序数组中出现的次数

统计一个数字在排序数组中出现的次数。例如，输入{1,2,3,3,3,3,4,5}和数字3，由于3在这个数组中出现了4次，因此输出4。

---

思路：改进运用二分查找
接下来我们思考如何更好地利用二分查找算法。假设我们是统计数字k在排序数组中出现的次数。在前面的算法中时间主要消耗在如何确定重复出现的数字的第一个k和最后一个k的位置上，有没有可能用二分查找算法直接找到第一个k及最后一个k呢？
我们先分析如何用二分查找算法在数组中找到第一个k。二分查找算法总是先拿数组中间的数字和k作比较。如果中间的数字比k大，那么k只有可能出现在数组的前半段，下一轮我们只在数组的前半段查找就可以了。如果中间的数字比k小，那么k只有可能出现在数组的后半段，下一轮我们只在数组的后半段查找就可以了。如果中间的数字和k相等呢？我们先判断这个数字是不是第一个k。如果位于中间数字的前面一个数字不是k，此时中间的数字刚好就是第一个k。如果中间数字的前面一个数字也是k，也就是说第一个k肯定在数组的前半段，下一轮我们仍然需要在数组的前半段查找。

基于以上思路，java参考代码如下：

public class NumberOfK {
    //遍历的话时间复杂度为o(n)
    //考虑到数组是排序好的，可使用二分法，时间复杂度o(logn)
    public static int getNumberOfK(int[] data,int length,int k){
    	int number=0;
    	
    	if(data!=null && length>0) {
    		int first = getFirstK(data,length,k,0,length-1);
    		int last = getLastK(data,length,k,0,length-1);
    		
    		if(first>-1 && last>-1)
    			number=last-first+1;
    	}
    	
        return number;
    }
    
    public static int getFirstK(int[] data,int length,int k,int start,int end){
    	if(start>end)
    		return -1;
    	
        if(data[0]>k || data[data.length-1]<k)
            return -1;
        
        int middleIndex=start+(end-start)/2;
        int middleData=data[middleIndex];
        if(middleData==k) {
        	if((middleIndex>0 && data[middleIndex-1]!=k)||middleIndex==0)
        		return middleIndex;
        	else
        		end=middleIndex-1;
        }
        else if(middleData>k)
        	end=middleIndex-1;
        else
        	start=middleIndex+1;
        
        return getFirstK(data,length,k,start,end);

    }
    public static int getLastK(int[] data,int length,int k,int start,int end){
       	if(start>end)
    		return -1;
    	
        if(data[0]>k || data[data.length-1]<k)
            return -1;
        
        int middleIndex=start+(end-start)/2;
        int middleData=data[middleIndex];
        if(middleData==k) {
        	if((middleIndex<length-1 && data[middleIndex+1]!=k)||middleIndex==length-1)
        		return middleIndex;
        	else
        		start=middleIndex+1;
        }
        else if(middleData>k)
        	end=middleIndex-1;
        else
        	start=middleIndex+1;
        
        return getLastK(data,length,k,start,end);
    }
    public static void main(String[] args){
        int[] data1 = new int[]{1,2,3,3,3,3,5,6};
        int[] data2 = new int[]{1,2,3,3,3,3,4,5};
        int[] data3 = new int[]{3,3,3,3,3,3,3,3};
        System.out.println(getNumberOfK(data1,8,4));
        System.out.println(getNumberOfK(data2,8,3));
        System.out.println(getNumberOfK(data3,8,3));
    }
}

测试用例：
a.功能测试（数组中包含要查找的数字；；数组中没有要查找的数字；要查找的数字在数组中出现一次或者多次）。
b.边界值测试（查找数组在的最大值、最小值；数组中只有一个数字）。
c.特殊输入测试（表示数组的指针为nullptr指针）。
参考：
https://www.jianshu.com/p/a5bda52fe134
http://www.cnblogs.com/edisonchou/p/4822740.html