原文链接: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

英文原文

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

You must write an algorithm with O(log n) runtime complexity.

 

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

中文题目

给定一个按照升序排列的整数数组 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

通过代码

高赞题解

思路分析：

• 不可以找到 target 以后，然后向两边扩散（线性查找），这样的话时间复杂度为 $O(N)$，这里 $N$ 是输入数组的长度；

• 应该使用两次二分查找，先找 target 第一次出现的位置，再找 target 最后一次出现的位置，注意分类讨论，并且把分类讨论的结果合并。

参考代码：

[]
public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return new int[]{-1, -1};
        }

        int firstPosition = findFirstPosition(nums, target);
        if (firstPosition == -1) {
            return new int[]{-1, -1};
        }

        int lastPosition = findLastPosition(nums, target);
        return new int[]{firstPosition, lastPosition};
    }

    private int findFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 小于一定不是解
            if (nums[mid] < target) {
                // 下一轮搜索区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // nums[mid] > target，下一轮搜索区间是 [left..mid]
                right = mid;
            }
        }

        if (nums[left] == target) {
            return left;
        }
        return -1;
    }

    private int findLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (nums[mid] > target) {
                // 下一轮搜索区间是 [left..mid - 1]
                right = mid - 1;
            } else 
                // 下一轮搜索区间是 [mid..right]
                left = mid;
            } 
        }
        return left;
    }
}

参考代码的补充说明：

findFirstPosition()，分成三种情况：下面的描述可能有一点啰嗦，但是很多时候问题并不难，我们需要仔细一点就不难做对。

情况 ① ：当 nums[mid] < target 时

• mid 一定不是 target 第一次出现的位置；
• 由于数组有序，mid 的左边一定比 nums[mid] 还小，因此 mid 的左边一定不是 target 第一次出现的位置；
• mid 的右边比 nums[mid] 还大，因此 mid 的右边有可能存在 target 第一次出现的位置。

因此下一轮搜索区间是 [mid + 1..right]，此时设置 left = mid + 1；

情况 ② ：当 nums[mid] == target 时

• mid 有可能是 target 第一次出现的位置；
• mid 的左边也有可能是 target 第一次出现的位置；
• mid 的右边一定不是 target 第一次出现的位置。

因此下一轮搜索区间在 [left..mid]，此时设置 right = mid。

情况 ③ ：当 nums[mid] > target 时

• mid 一定不是 target 第一次出现的位置；
• mid 的右边也一定不是 target 第一次出现的位置；
• mid 的左边有可能是 target 第一次出现的位置，因此下一轮搜索区间在 [left..mid - 1]，此时设置 right = mid - 1。

重点在这里：把情况 ② 和情况 ③ 合并，即当 nums[mid] >= target 的时候，下一轮搜索区间是 [left..mid]，此时设置 right = mid - 1。这样做是因为：只有当区间分割是 [left..mid] 和 [mid + 1..right] 的时候，while(left < right) 退出循环以后才有 left == right 成立。

findLastPosition() 也可以类似分析，这里省略。

在本题解中，while(left < right) 只表示退出循环以后有 left == right 成立，不表示搜索区间为左闭右开区间，本题解以及我的其它题解中，对循环不变量的定义均为：在 nums[left..right] 中查找目标元素。

复杂度分析：

• 时间复杂度：$O(\log N)$，这里 $N$ 是数组的长度，两个子问题都是二分查找，因此时间复杂度为对数级别；
• 空间复杂度：$O(1)$，只使用了常数个数的辅助变量。

统计信息

通过次数	提交次数	AC比率
383021	906013	42.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
第一个错误的版本	简单