升序数组出现次数

这种和快排的二分不一样，快排是两边都要保留，但是这里只需要保留一边就以可以了，所以可以用循环代替递归

递归法

public int GetNumberOfK(int [] array , int k) {
    if(array.length==0 || array==null){
        return 0;
    }
    if(k<array[0] || k>array[array.length-1]){
        return 0;
    }
    int index=getMid(array,k,0,array.length-1);
    if(index==-1){
        return 0;
    }
    int a=index-1;
    int b=index;
    int count=0;
    while(b!=array.length && array[b]==k){
        b++;
        count++;
    }
    while(a>=0 && array[a]==k){
        a--;
        count++;
    }
    return count;
}



public int getMid(int [] array,int k,int left ,int right){
    if(left>right){
        return -1;
    }
    int mid=(left+right)>>1;
    if(k==array[mid]){
        return mid ;
    }
    if(k<array[mid]){
       return  getMid(array,k,left,mid-1);
    } else{
       return  getMid(array,k,mid+1,right);
    }
}

循环法

public int GetNumberOfK(int [] array , int k) {
    if(array.length==0 || array==null){
        return 0;
    }
    if(k<array[0] || k>array[array.length-1]){
        return 0;
    }
    int index=getMid(array,k);
    if(index==-1){
        return 0;
    }
    int a=index-1;
    int b=index;
    int count=0;
    while(b!=array.length && array[b]==k){
        b++;
        count++;
    }
    while(a>=0 && array[a]==k){
        a--;
        count++;
    }
    return count;
}


public int getMid(int [] array,int k){
    int left =0;
    int right=array.length-1;
    int res=-1;
    while(left<=right){
        int mid=(left+right)>>1;
        if(array[mid]==k){
            res=mid;
            break;
        }else if(array[mid]<k){
            left=mid+1;
        } else {
            right=mid-1;
        }
    }
    return res;
}