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

题目描述

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

思路分析

• 通过 indexOf 和 lastIndexOf 查找边界
• 二分查找边界

代码实现

function findBou(arr, num, mode) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    console.log(arr, left, right, mid);
    if (arr[mid] < num) {
      left = mid;
    } else if (arr[mid] > num) {
      right = mid;
    } else if (mode == "left") {
      if (arr[mid - 1] != num) {
        console.log("left bound:", mid);
        return mid;
      }
      right = mid;
    } else if (mode == "right") {
      if (arr[mid + 1] != num) {
        console.log("right bound:", mid);
        return mid;
      }
      left = mid;
    }
  }
}

function countNum(arr, num) {
  if (arr[0] == arr[arr.length - 1]) {
    return arr.length;
  } else if (arr.length == 2 && (arr[0] == num || arr[1] == num)) {
    return 1;
  } else if (arr.length == 2 && [0] != num && arr[1] != num) {
    return -1;
  } else {
    return findBou(arr, num, "right") - findBou(arr, num, "left") + 1;
  }
}
arr = [1, 1, 1, 1];
console.log(countNum(arr, 3));