LeetCode 题解

LeetCode 第 34 题：“在排序数组中查找元素的第一个和最后一个位置”题解

题解地址：十分好用的二分查找法模板（Python 代码、Java 代码）。

说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。

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

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

你的算法时间复杂度必须是 O(log n) 级别。

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

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8 输出: [3,4] 示例 2:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

十分好用的二分查找法模板（Python 代码、Java 代码）

思路分析：毋庸置疑，肯定用二分法，二分法的核心思想是“夹逼法”或者称为“排除法”。

1、尽最大可能排除不符合题意的元素，在每一轮循环中不断减少候选区间的范围，直到候选区间收缩成 1 个数。

2、因为数组中很可能不存在目标值，因此在第 1 步使用“排除法”最后剩下的这个数，再判断一下它是否等于 target 即可。

我把这道题的两个子问题做了一下修改，并写出了关键部分：

1、子问题 1（“开始位置”）：找到等于 target 的第 11 个元素的索引，如果找不到等于 target 的数，返回 −1-1；

关键：如果小于，肯定不是解，此时 left = mid + 1。

2、子问题 2（“结束位置”）：找到等于 target 的最后 11 个元素的索引，如果找不到等于 target 的数，返回 −1-1。

关键：如果大于，肯定不是解：此时 right = mid - 1。

在「力扣 」第 35 题：“搜索插入位置”的题解《特别好用的二分查找法模板（Python 代码、Java 代码）》 里我写了如何使用二分查找法的模板。

下面给出的参考代码，并且在一些细节处给出了注释，如果你有疑问的话，不妨再看一看我上面给出的文章，相信你很容易找到答案。

参考代码：

Python 代码：

from typing import List


class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        size = len(nums)
        # 特判，这一步很重要，否则执行到后序方法可能会出现数组下标越界
        # 同时后序两个方法也不用做特殊判断了
        if size == 0:
            return [-1, -1]

        num1 = self.__find_lower_bound(nums, target)
        # 细节：如果左边界都搜索不到，右边界也没有必要看了
        if num1 == -1:
            return [-1, -1]

        num2 = self.__find_up_bound(nums, target)
        return [num1, num2]

    def __find_lower_bound(self, nums, target):
        # 找等于 target 的第 1 个数的索引，小于一定不符合要求
        size = len(nums)

        left = 0
        right = size - 1
        while left < right:
            # 根据分支逻辑，这里选择左中位数
            # mid = left + (right - left) // 2
            mid = (left + right) >> 1
            # 因为找大于等于 target 的第 1 个数，因此小于一定不符合要求
            # 把它写在分支的前面
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        # 因为有可能不存在目标元素，最后一定要单独判断一下
        if nums[left] != target:
            return -1
        return left

    def __find_up_bound(self, nums, target):
        # 找等于 target 的最后 1 个数的索引，大于一定不符合要求
        # 因为有可能不存在，最后一定要单独判断一下
        size = len(nums)
        left = 0
        right = size - 1
        while left < right:
            # 根据分支逻辑，这里选择右中位数
            # mid = left + (right - left + 1) // 2
            mid = (left + right + 1) >> 1
            # 因为找小于等于 target 的最后 1 个数，因此大于一定不符合要求
            # 把它写在分支的前面
            if nums[mid] > target:
                right = mid - 1
            else:
                left = mid
        # 因为有可能不存在目标元素，最后一定要单独判断一下
        if nums[left] != target:
            return -1
        return left


if __name__ == '__main__':
    solution = Solution()
    nums = [5, 7, 7, 8, 8, 10]
    target = 8
    result = solution.searchRange(nums, target)
    print(result)

Java 代码：

import java.util.Arrays;

public class Solution {

    public int[] searchRange(int[] nums, int target) {
        int len = nums.length;
        // 特判，这一步很重要，否则执行到后序方法可能会出现数组下标越界
        // 同时后序两个方法也不用做特殊判断了
        if (len == 0) {
            return new int[]{-1, -1};
        }

        int num1 = findLowerBound(nums, target);
        // 细节：如果左边界都搜索不到，右边界也没有必要看了
        if (num1 == -1) {
            return new int[]{-1, -1};
        }
        int num2 = findUpBound(nums, target);
        return new int[]{num1, num2};
    }


    private int findLowerBound(int[] nums, int target) {
        // 找等于 target 的第 1 个数的索引，小于一定不符合要求
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            // 根据分支逻辑，这里选择左中位数
            // int mid = left + (right - left) / 2;
            int mid = (left + right) >>> 1;
            // 因为找大于等于 target 的第 1 个数，因此小于一定不符合要求
            // 把它写在分支的前面
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        // 因为有可能不存在目标元素，最后一定要单独判断一下
        if (nums[left] != target) {
            return -1;
        }
        return left;
    }

    private int findUpBound(int[] nums, int target) {
        // 找等于 target 的最后 1 个数的索引，大于一定不符合要求
        // 因为有可能不存在，最后一定要单独判断一下
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            // 根据分支逻辑，这里选择右中位数
            // int mid = left + (right - left + 1) / 2;
            int mid = (left + right + 1) >>> 1;
            // 因为找小于等于 target 的最后 1 个数，因此大于一定不符合要求
            // 把它写在分支的前面
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        // 因为有可能不存在目标元素，最后一定要单独判断一下
        if (nums[left] != target) {
            return -1;
        }
        return left;
    }

    public static void main(String[] args) {
        int[] nums = {5, 7, 7, 8, 8, 10};
        int target = 8;
        Solution4 solution4 = new Solution4();
        int[] res = solution4.searchRange(nums, target);
        System.out.println(Arrays.toString(res));
    }
}

复杂度分析：

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

补充说明：

上面我把

int mid = left + (right - left) / 2;

注释掉，而选用

int mid = (left + right) >>> 1;

并且把

int mid = left + (right - left + 1) / 2;

注释掉，而选用

int mid = (left + right + 1) >>> 1;

的原因，大家可以参考我为「力扣」第 374 题：“猜数字大小”写的题解 《借本题说一说取中位数的写法（Python 代码、Java 代码）》。

← LeetCode 第 69 题：“x 的平方根”题解 →