34.在排序数组中查找元素的第一个和最后一个位置

LeetCode LeetCode 热题100 数组二分查找

发布时间 : 2000-01-10 00:03

字数:1.5k 阅读 :

评论:

34.在排序数组中查找元素的第一个和最后一个位置

34.在排序数组中查找元素的第一个和最后一个位置

34.1 题目

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9

34.2 题解

方法一：二分查找两次

思路

分别用二分查找找到目标值的左边界和右边界。查找左边界时，找到目标值后继续向左搜索；查找右边界时，找到目标值后继续向右搜索。两次二分查找的时间复杂度都是 O(log n)。

核心思想：二分查找变体，找到目标后继续搜索边界。

具体步骤：

查找左边界：
- 找到 target 后，记录位置并继续向左搜索（right = mid - 1）
查找右边界：
- 找到 target 后，记录位置并继续向右搜索（left = mid + 1）
返回 [leftBound, rightBound]。

举例：对于 nums = [5,7,7,8,8,10], target = 8：

查找左边界：
- mid=2, nums[2]=7 < 8，left=3
- mid=4, nums[4]=8 == 8，记录 bound=4，right=3
- mid=3, nums[3]=8 == 8，记录 bound=3，right=2
- left > right，结束，左边界为 3
查找右边界：
- mid=2, nums[2]=7 < 8，left=3
- mid=4, nums[4]=8 == 8，记录 bound=4，left=5
- mid=5, nums[5]=10 > 8，right=4
- left > right，结束，右边界为 4
结果：[3, 4]

复杂度分析

时间复杂度：O(log n)，两次二分查找。
空间复杂度：O(1)，只使用常数变量。

代码

// 方法一：二分查找两次，分别查找开始位置和结束位置
static int[] SearchRange1(int[] nums, int target)
{
    // 查找目标值的开始位置
    int start = FindBound(nums, target, true);
    // 查找目标值的结束位置
    int end = FindBound(nums, target, false);
    // 返回结果
    return new int[] { start, end };
}

// 查找目标值的边界位置
static int FindBound(int[] nums, int target, bool isFirst)
{
    int left = 0; // 左边界初始化为0
    int right = nums.Length - 1; // 右边界初始化为数组最后一个元素的索引
    int bound = -1; // 初始化边界值为-1

    while (left <= right) // 当左边界小于等于右边界时进行循环
    {
        int mid = left + (right - left) / 2; // 计算中间位置
        if (nums[mid] == target) // 如果中间位置的元素等于目标值
        {
            bound = mid; // 更新边界值为中间位置
            if (isFirst) // 如果查找的是开始位置
            {
                right = mid - 1; // 更新右边界为中间位置减1
            }
            else // 如果查找的是结束位置
            {
                left = mid + 1; // 更新左边界为中间位置加1
            }
        }
        else if (nums[mid] < target) // 如果中间位置的元素小于目标值
        {
            left = mid + 1; // 更新左边界为中间位置加1
        }
        else // 如果中间位置的元素大于目标值
        {
            right = mid - 1; // 更新右边界为中间位置减1
        }
    }

    return bound; // 返回边界值
}

34.3 代码

using System;

class Program
{
    static void Main()
    {
        #region 题目

        // 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。
        // 请你找出给定目标值在数组中的开始位置和结束位置。
        // 如果数组中不存在目标值 target，返回 [-1, -1]。
        // 你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

        // 示例 1：
        // 输入：nums = [5,7,7,8,8,10], target = 8
        // 输出：[3,4]

        // 示例 2：
        // 输入：nums = [5,7,7,8,8,10], target = 6
        // 输出：[-1,-1]

        // 示例 3：
        // 输入：nums = [], target = 0
        // 输出：[-1,-1]

        // 提示：
        // 0 <= nums.length <= 105
        // -109 <= nums[i] <= 109
        // nums 是一个非递减数组
        // -109 <= target <= 109

        #endregion

        #region 测试

        // 示例 1
        int[] nums1 = { 5, 7, 7, 8, 8, 10 };
        int target1 = 8;
        int[] result1 = SearchRange1(nums1, target1);
        Console.WriteLine($"示例1 方法1 输出：[{result1[0]}, {result1[1]}]");

        // 示例 2
        int[] nums2 = { 5, 7, 7, 8, 8, 10 };
        int target2 = 6;
        int[] result2 = SearchRange1(nums2, target2);
        Console.WriteLine($"示例2 方法1 输出：[{result2[0]}, {result2[1]}]");


        // 示例 3
        int[] nums3 = { };
        int target3 = 0;
        int[] result3 = SearchRange1(nums3, target3);
        Console.WriteLine($"示例3 方法1 输出：[{result3[0]}, {result3[1]}]");

        #endregion
    }

    #region 答案

    // 方法一：二分查找两次，分别查找开始位置和结束位置
    static int[] SearchRange1(int[] nums, int target)
    {
        // 查找目标值的开始位置
        int start = FindBound(nums, target, true);
        // 查找目标值的结束位置
        int end = FindBound(nums, target, false);
        // 返回结果
        return new int[] { start, end };
    }

    // 查找目标值的边界位置
    static int FindBound(int[] nums, int target, bool isFirst)
    {
        int left = 0; // 左边界初始化为0
        int right = nums.Length - 1; // 右边界初始化为数组最后一个元素的索引
        int bound = -1; // 初始化边界值为-1

        while (left <= right) // 当左边界小于等于右边界时进行循环
        {
            int mid = left + (right - left) / 2; // 计算中间位置
            if (nums[mid] == target) // 如果中间位置的元素等于目标值
            {
                bound = mid; // 更新边界值为中间位置
                if (isFirst) // 如果查找的是开始位置
                {
                    right = mid - 1; // 更新右边界为中间位置减1
                }
                else // 如果查找的是结束位置
                {
                    left = mid + 1; // 更新左边界为中间位置加1
                }
            }
            else if (nums[mid] < target) // 如果中间位置的元素小于目标值
            {
                left = mid + 1; // 更新左边界为中间位置加1
            }
            else // 如果中间位置的元素大于目标值
            {
                right = mid - 1; // 更新右边界为中间位置减1
            }
        }

        return bound; // 返回边界值
    }

    #endregion
}

34.4 运行结果

示例1 方法1 输出：[3, 4]
示例2 方法1 输出：[-1, -1]
示例3 方法1 输出：[-1, -1]

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com