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

文档摘要

数字在排序数组中出现的次数题目链接牛客网题目描述解题思路只要能找出给定的数字 k 在有序数组第一个位置和最后一个位置，就能知道该数字出现的次数。先考虑如何实现寻找数字在有序数组的第一个位置。正常的二分查找如下，在查找到给定元素 k 之后，立即返回当前索引下标。但是在查找第一个位置时，找到元素之后应该继续往前找。也就是当 nums[m]\>=k 时，在左区间继续查找，左区间应该包含 m 位置。查找最后一个位置可以转换成寻找 k+1 的第一个位置，并再往前移动一个位置。需要注意以上实现的查找第一个位置的 binarySearch 方法，h 的初始值为 nums.length，而不是 nums.length - 1。先看以下示例：如果 h 的取值为 nums.