题解 | #数字在升序数组中出现的次数#
数字在升序数组中出现的次数
https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2
想到了暴力解法和二分法，暴力解法时间复杂度为O(n)不符合要求，二分法为O(logn)符合要求，下面是二分法：
#算法题#
function GetNumberOfK(data, k){
if (data == null || data.length == 0) return 0;
return UpperBound(data, k) - LowerBound(data, k);
}
function LowerBound(data, k){ // 找第一个大于等于k的下标
let l = 0, r = data.length, mid;
while (l < r ) {
mid = l + ((r - l) >> 1);
if (data[mid] >= k) r = mid;
else l = mid + 1;
}
return r;
}
function UpperBound(data, k){ // 找第一个大于k的下标
let l = 0, r = data.length, mid;
while (l < r ) {
mid = l + ((r - l) >> 1);
if (data[mid] > k) r = mid;
else l = mid + 1;
}
return r;
}
module.exports = {
GetNumberOfK : GetNumberOfK
};
#算法题#