题目

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

方法

参考：https://blog.csdn.net/mbskypan/article/details/89495140 方法二
复杂度：2nlogn

代码

function GetNumberOfK (data, k) {
  // write code here
  let first = getFirst(data, k, 0, data.length - 1)
  let last = getLast(data, k, 0, data.length - 1)
  return first === -1 ? 0 : last - first + 1
}

function getFirst (arr, k, s, e) {
  if (s > e) return -1
  let middle = (s + e) >> 1
  if (arr[middle] > k) {
    return getFirst(arr, k, s, middle - 1)
  } else if (arr[middle] < k) {
    return getFirst(arr, k, middle + 1, e)
  } else if (middle - 1 >= s && arr[middle - 1] === k) {
    return getFirst(arr, k, s, middle - 1)
  } else {
    return middle
  }
}

function getLast (arr, k, s, e) {
  if (s > e) return -1
  let middle = (s + e) >> 1
  if (arr[middle] > k) {
    return getLast(arr, k, s, middle - 1)
  } else if (arr[middle] < k) {
    return getLast(arr, k, middle + 1, e)
  } else if (middle + 1 <= e && arr[middle + 1] === k) {
    return getLast(arr, k, middle + 1, e)
  } else {
    return middle
  }
}