数字在排序数组中出现的次数

题目描述

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

• 用二分查找找到第一次出现的地方和最后一次出现的地方，两者相减再加1即为出现的次数。

function GetNumberOfK(data, k)
{
    // write code here
    if( getBegin(data,k) == -1 && getEnd(data,k) == -1 )return 0;
    return getEnd(data,k)-getBegin(data,k)+1;
}
function getBegin(data,k){
    let left=0;
    let right=data.length-1;
    let mid=right+left>>1;
    while(left<=right){
        if(data[mid]<k){
            left=mid+1;
        }else if(data[mid]>k){
            right=mid-1;
        }else if(data[mid-1]===k&&mid-1>=0){
           right=mid-1;
        }else{
            return mid;
        }
        mid=right+left>>1
    }
    return -1;
}
function getEnd(data,k){
    let left =0;
    let right=data.length-1;
    let mid=right+left>>1;
    while(left<=right){
        if(data[mid]<k){
            left=mid+1;
        }else if(data[mid]>k){
            right=mid-1;
        }else if(data[mid+1]==k&&mid+1<=data.length){
            left=mid+1;
        }else{
            return mid;
        }
        mid=right+left>>1
    }
    return -1;
}