Medium

题目描述

给你一个按照非递减顺序排列的整数数组 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

解题思路

解题思路

这道题要求在有序数组中找到目标值的第一个和最后一个位置，且时间复杂度为 O(log n)，这明显提示我们需要使用二分查找。

核心思想： 由于数组是有序的，相同的元素必定连续出现。我们可以通过两次二分查找来分别找到目标值的左边界和右边界。

具体做法：

  1. 寻找左边界：使用二分查找找到第一个等于 target 的位置

    • 当 nums[mid] >= target 时，答案可能在左半部分，移动 right
    • 当 nums[mid] < target 时，答案必定在右半部分，移动 left

  2. 寻找右边界：使用二分查找找到最后一个等于 target 的位置

    • 当 nums[mid] > target 时，答案必定在左半部分，移动 right
    • 当 nums[mid] <= target 时，答案可能在右半部分，移动 left

优化思路： 也可以先用标准二分查找确定 target 是否存在，然后分别向左右扩展寻找边界，但两次二分查找的方法更加优雅且保证了 O(log n) 的复杂度。

关键在于理解边界条件的处理，确保能够准确找到第一个和最后一个目标元素的位置。

代码实现

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};
        
        int left = findLeft(nums, target);
        int right = findRight(nums, target);
        
        return {left, right};
    }
    
private:
    int findLeft(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return (left < nums.size() && nums[left] == target) ? left : -1;
    }
    
    int findRight(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return (right >= 0 && nums[right] == target) ? right : -1;
    }
};

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if not nums:
            return [-1, -1]
        
        def findLeft(target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] >= target:
                    right = mid - 1
                else:
                    left = mid + 1
            return left if left < len(nums) and nums[left] == target else -1
        
        def findRight(target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = (left + right) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return right if right >= 0 and nums[right] == target else -1
        
        return [findLeft(target), findRight(target)]

public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        if (nums.Length == 0) return new int[] {-1, -1};
        
        int left = FindLeft(nums, target);
        int right = FindRight(nums, target);
        
        return new int[] {left, right};
    }
    
    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) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return (left < nums.Length && nums[left] == target) ? left : -1;
    }
    
    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 (right >= 0 && nums[right] == target) ? right : -1;
    }
}

var searchRange = function(nums, target) {
    const findFirst = (nums, target) => {
        let left = 0, right = nums.length - 1;
        let result = -1;
        
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] === target) {
                result = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    };
    
    const findLast = (nums, target) => {
        let left = 0, right = nums.length - 1;
        let result = -1;
        
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            if (nums[mid] === target) {
                result = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    };
    
    const first = findFirst(nums, target);
    const last = findLast(nums, target);
    
    return [first, last];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(log n)
空间复杂度O(1)

说明：

  • 时间复杂度：进行了两次二分查找，每次都是 O(log n)，总体仍为 O(log n)
  • 空间复杂度：只使用了常数个额外变量，空间复杂度为 O(1)

相关题目