每日一题--数字在排序数组中出现的次数

一下子想到的解法是遍历，时间复杂度为O（n）
改进：排序的数组，想到二分查找查找数字的方法，这里迁移为找第一次出现该数字和最后一次出现该数字，最后得到数组中该数字出现的总次数。
如何在数组中找到第一个数字出现的位置？？？？
二分查找总是先拿中间的值与k作比较，如果中间数字大于k，则第一个出现的肯定在数组的前半段，如果中间数字小于k，则第一个出现的肯定在数组的前半段，较为复杂的是：中间数字等于k,如果中间数字的前一个数字也为k，则第一次出现的在前半段，否则中间数字的位置即为第一次出现的位置。采用递归

考察：知识迁移能力

代码：

package core;

/**问题描述:统计一个数字在排序数组中出现的次数
 * 输入：{1,2,3,3,3，3,3,4,5}和3
 * 输出：5
 * Created by lxq on 2017/9/12.
 */
public class Problem2 {
public static void main(String[] args){
        Problem2 problem2 = new Problem2();
int[]array = {1,2,3,3,3,3,4,5};
int k =  problem2.getNumberOfK(array,3);
        System.out.println(k);
    }
public int getNumberOfK(int[] array,int k){
int number = 0;
if(array!=null){
int first = getFirstK(array,k,0,array.length-1);
int last = getLastK(array,k,0,array.length-1);
if(first>-1&&last>-1){
                number = last-first+1;
            }
        }
return number;
    }

//利用二分查找，时间复杂度为O(logn)，找到到最后一个k在数组中的下标
private int getLastK(int[] array, int k, int start, int end) {
if(start>end)
return -1;
int middleIndex = (end+start)/2;
int middleData = array[middleIndex];
if(middleData==k){
//中间数字是最后一个k,
//特殊情况：中间数字在数组中的最后位置，肯定就是最后一个
if((middleIndex<array.length-1&&array[middleIndex+1]!=k)||middleIndex==array.length-1)
return middleIndex;
//后面位置也是k,说明最后一个k在后半段
else
                start = middleIndex+1;
        }
else if(middleData>k){
//最后一个k在前半段
            end = middleIndex-1;
        }else {
//最后一个k在后半段
            start = middleIndex+1;
        }
return getLastK(array,k,start,end);
    }

//利用二分查找，时间复杂度为O(logn),找到第一个k在数组中的下标
private int getFirstK(int[] array, int k, int start, int end) {
if(start>end)
return -1;  //不包含k返回-1
int middleIndex = (end+start)/2;
int middleData = array[middleIndex];
//如果中间数字==k,
if(middleData==k){
//中间数的前面一个数字是否也是k
if((middleIndex>0&&array[middleIndex-1]!=k)||middleIndex==0)
return middleIndex;
//第一个数字在前半段，递归调用前半段
else
                end = middleIndex-1;
        }
//中间数字大于k,在前半段递归调用
else if(middleData>k){
            end = middleIndex-1;
        }
//中间数字小于k,在后半段递归调用
else {
            start = middleIndex+1;
        }
return getFirstK(array,k,start,end);
    }
}