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

Categories:

题目描述
思路分析
1. 解法一：二分查找左右边界（推荐）
2. 解法二：分别查找左右边界
相似题目

题目描述

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

给定一个排序数组 nums 和一个目标值 target，请你在数组中查找目标值 target 的出现次数。如果 target 不存在于数组中，则返回 0。

示例 1： 输入：nums = [5, 7, 7, 8, 8, 10], target = 8 输出：2 解释：8 在数组中出现了两次。

示例 2： 输入：nums = [5, 7, 7, 8, 8, 10], target = 6 输出：0 解释：6 在数组中不存在。

提示：

0 <= nums.length <= 10^5

-10^9 <= nums[i] <= 10^9

思路分析

解法一：二分查找左右边界（推荐）

核心思路：

利用二分查找分别找到 target 在排序数组中的左边界（第一个出现的位置）和右边界（最后一个出现位置的下一个位置）。

左边界：找满足 nums[mid] >= target 的最小下标，即第一个 >= target 的位置。

右边界：找满足 nums[mid] > target 的最小下标，即第一个 > target 的位置。

target 的出现次数 = 右边界 - 左边界。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示数组长度，两次二分查找各 O(log n)。

空间复杂度：O(1)，仅使用常数个辅助变量。

class Solution {

    public int search(int[] nums, int target) {
        // 分别找左边界和右边界，相减即为出现次数
        return findLeft(nums, target + 1) - findLeft(nums, target);
    }

    // 查找第一个大于等于 target 的位置（左边界）
    private int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

func search(nums []int, target int) int {
    // 分别找左边界和右边界，相减即为出现次数
    return findLeft(nums, target+1) - findLeft(nums, target)
}

// findLeft 查找第一个大于等于 target 的位置（左边界）
func findLeft(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

解法二：分别查找左右边界

核心思路：

使用两个独立的二分查找函数，分别求出 target 的最左位置和最右位置后一位。

findLeft：当 nums[mid] < target 时收缩左边界，否则收缩右边界，最终 left 落在第一个 target 的位置。

findRight：当 nums[mid] <= target 时收缩左边界，否则收缩右边界，最终 left 落在最后一个 target 的下一个位置。

出现次数 = findRight(target) - findLeft(target)。

复杂度分析：

时间复杂度：O(log n)，其中 n 表示数组长度，两次二分查找各 O(log n)。

空间复杂度：O(1)，仅使用常数个辅助变量。

class Solution {

    public int search(int[] nums, int target) {
        return findRight(nums, target) - findLeft(nums, target);
    }

    // 查找 target 第一次出现的位置
    private int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    // 查找 target 最后一次出现位置的下一个位置
    private int findRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

func search(nums []int, target int) int {
    return findRight(nums, target) - findLeft(nums, target)
}

// findLeft 查找 target 第一次出现的位置
func findLeft(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

// findRight 查找 target 最后一次出现位置的下一个位置
func findRight(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        mid := left + (right-left)/2
        if nums[mid] <= target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return left
}

相似题目

题目	难度	考察点
34. 在排序数组中查找元素的第一个和最后一个位置	中等	二分查找 / 左右边界
35. 搜索插入位置	简单	二分查找 / 边界
278. 第一个错误的版本	简单	二分查找 / 左边界
162. 寻找峰值	中等	二分查找 / 边界条件
153. 寻找旋转排序数组中的最小值	中等	二分查找 / 旋转数组
704. 二分查找	简单	二分查找 / 基础
744. 寻找比目标字母大的最小字母	简单	二分查找 / 边界

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/54309961