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

发表于 | 分类于

题目

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

思路

二分查找
找到数字开始的位置和数字结束的位置，然后相减

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
function GetNumberOfK(data, k) {
  if (getEnd(data, k) === -1 && getBegin(data, k) === -1) return 0;
  return getEnd(data, k) - getBegin(data, k) + 1;
}
function getBegin(data, k) {
  let [left, right] = [0, data.length - 1];
  let mid = left + right >> 1;
  while (left <= right) {
    if (data[mid] > k) {
      right = mid - 1;
    } else if (data[mid] < k) {
      left = mid + 1;
    } else if (mid - 1 >= 0 && data[mid - 1] === k) {
      right = mid - 1;
    } else return mid;
    mid = left + right >> 1;
  }
  return -1;
}
function getEnd(data, k) {
  let [left, right] = [0, data.length - 1];
  let mid = left + right >> 1;
  while (left <= right) {
    if (data[mid] > k) {
      right = mid - 1;
    } else if (data[mid] < k) {
      left = mid + 1;
    } else if (mid + 1 < data.length && data[mid + 1] === k) {
      left = mid + 1;
    } else return mid;
    mid = left + right >> 1;
  }
  return -1;
}