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

力扣题目链接 (opens new window)

题目描述

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

思路

这道题如果直接遍历数组，遇到 target 时记录起点和终点，也能做出来。

但题目要求 O(log n)，很明显不能线性遍历，应该想到二分查找。

很多录友会说：二分不是找到 target 后直接返回吗？

本题不一样。数组里可能有多个 target，找到一个还不够，我们还要继续确认它是不是最左边或最右边的那个。

所以本题要做两次二分：

• 第一次找 target 的左边界。
• 第二次找 target 的右边界。

找左边界时，如果 nums[mid] == target，不能立刻返回。此时先记录 mid，然后继续去左边找：

right = mid - 1

因为左侧可能还有 target。

找右边界则反过来：命中 target 后先记录 mid，再继续去右边找：

left = mid + 1

二分查找的关键还是区间不变量。这里使用左闭右闭区间 [left, right]，所以循环条件是 left <= right。

模拟过程

以 nums = [5,7,7,8,8,10]、target = 8 为例。

寻找左边界

先看 mid = 2，nums[mid] = 7 < 8，左边不可能有答案，令 left = 3。

接着 mid = 4，命中 8。先记录 4，但它未必是最左边的 8，所以令 right = 3 继续向左收缩。

最后 mid = 3，再次命中 8，更新答案为 3，继续收缩后区间为空。左边界就是 3。

寻找右边界

前两轮同样先排除 7 所在的左侧，然后命中 mid = 4。

这次我们要找最右的 8，所以记录 4 后令 left = 5。随后 nums[5] = 10 > 8，右侧不可能有答案，搜索结束。

想清楚以下几点，本题才算理解透彻：

• 找到 target 后不能直接返回。
• 找左边界时，命中后继续 right = mid - 1。
• 找右边界时，命中后继续 left = mid + 1。
• 初始答案设为 -1，自然就能处理 target 不存在和空数组。

解题代码

class Solution {
public:
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                if (nums[mid] == target) result = mid; // 先记录，再继续向左找
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int result = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                if (nums[mid] == target) result = mid; // 先记录，再继续向右找
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        return {getLeftBorder(nums, target), getRightBorder(nums, target)};
    }
};

复杂度分析

时间复杂度：O(log n)，进行了两次二分查找。空间复杂度：O(1)。

其他语言

Python3

class Solution:
    def searchRange(self, nums, target):
        def get_left():
            left, right, result = 0, len(nums) - 1, -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] >= target:
                    if nums[mid] == target:
                        result = mid  # 记录后仍要继续向左找
                    right = mid - 1
                else:
                    left = mid + 1
            return result

        def get_right():
            left, right, result = 0, len(nums) - 1, -1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] <= target:
                    if nums[mid] == target:
                        result = mid  # 记录后仍要继续向右找
                    left = mid + 1
                else:
                    right = mid - 1
            return result

        return [get_left(), get_right()]

Java

class Solution {
    private int getLeftBorder(int[] nums, int target) {
        int left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                if (nums[mid] == target) result = mid; // 记录后继续向左找
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    }

    private int getRightBorder(int[] nums, int target) {
        int left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                if (nums[mid] == target) result = mid; // 记录后继续向右找
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    public int[] searchRange(int[] nums, int target) {
        return new int[] {getLeftBorder(nums, target), getRightBorder(nums, target)};
    }
}

Go

func searchRange(nums []int, target int) []int {
    getLeftBorder := func() int {
        left, right, result := 0, len(nums)-1, -1
        for left <= right {
            mid := left + (right-left)/2
            if nums[mid] >= target {
                if nums[mid] == target {
                    result = mid // 记录后继续向左找
                }
                right = mid - 1
            } else {
                left = mid + 1
            }
        }
        return result
    }

    getRightBorder := func() int {
        left, right, result := 0, len(nums)-1, -1
        for left <= right {
            mid := left + (right-left)/2
            if nums[mid] <= target {
                if nums[mid] == target {
                    result = mid // 记录后继续向右找
                }
                left = mid + 1
            } else {
                right = mid - 1
            }
        }
        return result
    }

    return []int{getLeftBorder(), getRightBorder()}
}

JS

var searchRange = function(nums, target) {
    const getLeftBorder = () => {
        let left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            if (nums[mid] >= target) {
                if (nums[mid] === target) result = mid; // 记录后继续向左找
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return result;
    };

    const getRightBorder = () => {
        let left = 0, right = nums.length - 1, result = -1;
        while (left <= right) {
            const mid = left + Math.floor((right - left) / 2);
            if (nums[mid] <= target) {
                if (nums[mid] === target) result = mid; // 记录后继续向右找
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    };

    return [getLeftBorder(), getRightBorder()];
};

与代码随想录联系

本题就是704. 二分查找的边界版本。

704 题中找到 target 就可以返回，而本题要继续收缩区间，才能确认目标值两端的位置。这也正好说明，二分查找不只是“找一个数”，更重要的是维护好每一轮的搜索区间。

建议录友把这两道题放在一起看：

• 704. 二分查找：练习左闭右闭、左闭右开的区间不变量。
• 本题：练习命中 target 后，如何继续收缩来寻找边界。