在排序数组中查找数字 I（二分法）+读1

目录

• 1 题目描述
• 2 解题（Java）
• • 2.1 解题思路
  • 2.2 代码
• 3 复杂性分析

1 题目描述

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

示例 1:

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

输出: 2

示例 2:

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

输出: 0

限制：

0 <= 数组长度 <= 50000

2 解题（Java）

2.1 解题思路

1. 本题要求统计数字 target的出现次数，可转化为：使用二分法分别找到 左边界 left 和 右边界 right ，易得数字 target 的数量为 right - left - 1；

class Solution {
    public int search(int[] nums, int target) {
        // 查找右边界
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] <= target) i = m + 1;
            else j = m - 1;
        }
        int right = i;

        // 查找左边界
        i = 0; j = nums.length - 1;
        while (i <= j) {
            int m = (i + j) / 2;
            if (nums[m] >= target) j = m - 1;
            else i = m + 1;
        }
        int left = j;
        return right - left - 1;
    }
}
           

1. 由于数组 nums中元素都为整数，因此可以分别二分查找 target和 target - 1 的右边界，将两结果相减并返回即可;

2.2 代码

class Solution {
    public int search(int[] nums, int target) {
        return search_right(nums, target) - search_right(nums, target - 1);
    }
    int search_right(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] <= target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}
           

3 复杂性分析

• 时间复杂度 O(log N) ： 二分法为对数级别复杂度；
• 空间复杂度 O(1) ： 几个变量使用常数大小的额外空间；

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof