算法练习24：在排序数组中查找数字 I(leetcode Off

题目

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

输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

解法1：遍历1次计数

遍历一次数组，如果有target则计数+1，结束遍历后输入总计数

• 时间复杂度：O(n)
• 空间复杂度：O(1)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let res = 0;
    for(let i = 0; i < nums.length; i++) {
        if(nums[i] === target) res++;
    }
    return res;
};

解法2：使用二分法

递归2分，每次找到中位数下标（right - left）/2 向下取整 + left，对比中位数和目标数的大小：

• 如果中位数 > 目标数，则继续递归左半部分的数组
• 如果中位数 < 目标数，则继续递归查找右半部分数组
• 如果中位数 = 目标数，则只能分别递归左半部分和右半部分数组

var search = function(nums, target) {
  if(!nums.length) return 0;
  let res = 0;
  function getNum(left ,right) {
      if(right < left) return;
      if(right === left) {
          if(nums[right] === target) res++;
          return;
      }
      let middle = ((right - left) >> 1) + left
      if(nums[middle] === target) {
        res++;
        getNum(left, middle - 1)
        getNum(middle + 1, right)
      }else if(nums[middle] > target) {
        getNum(left, middle - 1)
      }else {
        getNum(middle + 1, right)
      } 
  }
  getNum(0, nums.length - 1)
  return res;
};

• 时间复杂度： O(logn)，每次都2分，也就是都是/2操作
• 空间复杂度：O(n/2) => O(n)