53-Ⅰ 在排序数组中查找数字 Ⅰ

剑指 Offer 53 - I. 在排序数组中查找数字 I

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

解题思路：

假设有一个大小为 $target$ 的数字要插入数组 $nums$，根据选择排序的思路，我们可以想到这个数组要插入到 target 的右边界的后面，记这个位置为 $right$。

假设有一个大小为 $x = target-1$ 的数字要插入数组 $nums$，根据前面的叙述，$x$ 应该插在数组中 x 的有边界的后面，记这个位置为 $left$。

那么 $left$ 和 $right$ 有什么关系呢？

可以得知，$left$ 和 $right$ 中间夹着的就是 $target$ 元素，$right - left$ 就是 $target$ 出现的次数。

代码：

public int search(int[] nums, int target) {
    return helper(nums, target) - helper(nums, target - 1);
}

/**
 * 找到一个右边界，可以让 target 插入
 */
private int helper(int[] nums, int target) {
    int i = 0, j = nums.length - 1;
    while (i <= j) {
        int mid = (i + j) / 2;
        if (nums[mid] <= target) {
            i = mid + 1;
        } else {
            j = mid - 1;
        }
    }
    return i;
}

复杂度分析

• 时间复杂度$O(logN)$：二分法为对数级别的复杂度。
• 空间复杂度$O(1)$：辅助变量占用常数大小的额外空间。