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

作者：沉默王二
发布时间：2022-08-30T08:31:23.482+0800

---

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

题意

给你一个数组nums[]和一个target值，让你求target值在数组nums[]中出现的第一个位置和最后一个位置。

如果nums[]中没有出现过target，则返回{-1,-1}。

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

难度

中等

示例

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

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

分析

之前，我们利用二分查找法在一个有序数组中查找某个值，本题要求我们查找目标值 target 在有序数组中出现的第一个位置和最后一个位置，于是，我们很自然而然就想到了二分查找。

可是怎么去使用二分查找法呢？

一开始，我们可能会想到直接查找数组中是否存在这个target值，然后再向左右扩展，可是这个思路如果遇到nums = [5,5,5,5,5], target = 5的情况，就需要遍历整个数组！时间复杂度就变成了，而不是题目要求的。

怎么办呢？

如果用C++来解题的话，可以利用它自带的两个二分查找函数——lower_bound()和upper_bound()，lower_bound()会返回大于或者等于 target 的第一个元素的位置，upper_bound()会返回大于 target 的第一个元素。

那此时，我们要使用 Java 来解题，那能不能参考这两个函数来求出这道题的答案呢？

先利用lower_bound()找出大于或等于 target 的第一个元素的位置，然后判断它是不是target，如果不是，那么就说明nums[]中并不存在 target ，如果有，我们再利用upper_bound()，找出大于 target 的第一个元素，而这个元素的位置 - 1 就是 target 的最后一个位置。

那么接下来就是利用 Java 来实现lower_bound()和upper_bound()这两个方法，实际上做法和一般的二分查找差别不大，lower_bound()只需要在 大于 的时候调整lef，让它能够尽量到达 target，而等于的时候调整rig，让它接近 target 的第一个位置，而lower_bound()只需要在 大于等于 的时候，调整lef让它 ”越过“ target 即可。

听描述好像还有点云里雾里，没事，我们来看一下代码就可以豁然开朗了。

class Solution {

        while (lef < rig) {            int mid = lef + (rig - lef) / 2;            if (target > nums[mid])//不同于upperBound()的地方                lef = mid + 1;            else                rig = mid;        }        return lef;    }    private int upperBound(int[] nums, int lef, int rig, int target) {        while (lef < rig) {            int mid = lef + (rig - lef) / 2;            if (target >= nums[mid])//不同于lowerBound()的地方                lef = mid + 1;            else                rig = mid;        }        return lef;    }    public int[] searchRange(int[] nums, int target) {        if(nums.length == 0)            return new int[]{-1, -1};        int lef = lowerBound(nums,0,nums.length - 1,target);        int rig = upperBound(nums,0,nums.length - 1,target);        if(nums[lef] != target)            return new int[]{-1, -1};        if(lef == rig)            return new int[]{lef,lef};        if(nums[rig] != target)            return new int[]{lef,rig - 1};        return new int[]{lef,rig};    }}

最后，我们需要注意一下边界的问题，如果所有元素都小于 target ，lowerBound()会返回末尾，而所有元素都小于等于 target ，upperBound()也会返回末尾，所以我们这个地方需要特判一下即可。

结果非常不错，因为两次都是利用二分查找，所以时间复杂度只有，而且不会被极端数据卡到。

总结

其实本题还是二分查找的变形，但凡是在有序的数据里面去查找，或者说，答案具有单调的性质，我们都可以尝试二分来解决。

力扣链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 720 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

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

题意

给你一个数组nums[]和一个target值，让你求target值在数组nums[]中出现的第一个位置和最后一个位置。

如果nums[]中没有出现过target，则返回{-1,-1}。

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

难度

中等

示例

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

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

分析

之前，我们利用二分查找法在一个有序数组中查找某个值，本题要求我们查找目标值 target 在有序数组中出现的第一个位置和最后一个位置，于是，我们很自然而然就想到了二分查找。

可是怎么去使用二分查找法呢？

一开始，我们可能会想到直接查找数组中是否存在这个target值，然后再向左右扩展，可是这个思路如果遇到nums = [5,5,5,5,5], target = 5的情况，就需要遍历整个数组！时间复杂度就变成了，而不是题目要求的。

怎么办呢？

如果用C++来解题的话，可以利用它自带的两个二分查找函数——lower_bound()和upper_bound()，lower_bound()会返回大于或者等于 target 的第一个元素的位置，upper_bound()会返回大于 target 的第一个元素。

那此时，我们要使用 Java 来解题，那能不能参考这两个函数来求出这道题的答案呢？

先利用lower_bound()找出大于或等于 target 的第一个元素的位置，然后判断它是不是target，如果不是，那么就说明nums[]中并不存在 target ，如果有，我们再利用upper_bound()，找出大于 target 的第一个元素，而这个元素的位置 - 1 就是 target 的最后一个位置。

那么接下来就是利用 Java 来实现lower_bound()和upper_bound()这两个方法，实际上做法和一般的二分查找差别不大，lower_bound()只需要在 大于 的时候调整lef，让它能够尽量到达 target，而等于的时候调整rig，让它接近 target 的第一个位置，而lower_bound()只需要在 大于等于 的时候，调整lef让它 ”越过“ target 即可。

听描述好像还有点云里雾里，没事，我们来看一下代码就可以豁然开朗了。

class Solution {

        while (lef < rig) {            int mid = lef + (rig - lef) / 2;            if (target > nums[mid])//不同于upperBound()的地方                lef = mid + 1;            else                rig = mid;        }        return lef;    }    private int upperBound(int[] nums, int lef, int rig, int target) {        while (lef < rig) {            int mid = lef + (rig - lef) / 2;            if (target >= nums[mid])//不同于lowerBound()的地方                lef = mid + 1;            else                rig = mid;        }        return lef;    }    public int[] searchRange(int[] nums, int target) {        if(nums.length == 0)            return new int[]{-1, -1};        int lef = lowerBound(nums,0,nums.length - 1,target);        int rig = upperBound(nums,0,nums.length - 1,target);        if(nums[lef] != target)            return new int[]{-1, -1};        if(lef == rig)            return new int[]{lef,lef};        if(nums[rig] != target)            return new int[]{lef,rig - 1};        return new int[]{lef,rig};    }}

最后，我们需要注意一下边界的问题，如果所有元素都小于 target ，lowerBound()会返回末尾，而所有元素都小于等于 target ，upperBound()也会返回末尾，所以我们这个地方需要特判一下即可。

结果非常不错，因为两次都是利用二分查找，所以时间复杂度只有，而且不会被极端数据卡到。

总结

其实本题还是二分查找的变形，但凡是在有序的数据里面去查找，或者说，答案具有单调的性质，我们都可以尝试二分来解决。

力扣链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 720 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

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

题意

给你一个数组nums[]和一个target值，让你求target值在数组nums[]中出现的第一个位置和最后一个位置。

如果nums[]中没有出现过target，则返回{-1,-1}。

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

难度

中等

示例

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

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

分析

之前，我们利用二分查找法在一个有序数组中查找某个值，本题要求我们查找目标值 target 在有序数组中出现的第一个位置和最后一个位置，于是，我们很自然而然就想到了二分查找。

可是怎么去使用二分查找法呢？

一开始，我们可能会想到直接查找数组中是否存在这个target值，然后再向左右扩展，可是这个思路如果遇到nums = [5,5,5,5,5], target = 5的情况，就需要遍历整个数组！时间复杂度就变成了，而不是题目要求的。

怎么办呢？

如果用C++来解题的话，可以利用它自带的两个二分查找函数——lower_bound()和upper_bound()，lower_bound()会返回大于或者等于 target 的第一个元素的位置，upper_bound()会返回大于 target 的第一个元素。

那此时，我们要使用 Java 来解题，那能不能参考这两个函数来求出这道题的答案呢？

先利用lower_bound()找出大于或等于 target 的第一个元素的位置，然后判断它是不是target，如果不是，那么就说明nums[]中并不存在 target ，如果有，我们再利用upper_bound()，找出大于 target 的第一个元素，而这个元素的位置 - 1 就是 target 的最后一个位置。

那么接下来就是利用 Java 来实现lower_bound()和upper_bound()这两个方法，实际上做法和一般的二分查找差别不大，lower_bound()只需要在 大于 的时候调整lef，让它能够尽量到达 target，而等于的时候调整rig，让它接近 target 的第一个位置，而lower_bound()只需要在 大于等于 的时候，调整lef让它 ”越过“ target 即可。

听描述好像还有点云里雾里，没事，我们来看一下代码就可以豁然开朗了。

class Solution {

        while (lef < rig) {            int mid = lef + (rig - lef) / 2;            if (target > nums[mid])//不同于upperBound()的地方                lef = mid + 1;            else                rig = mid;        }        return lef;    }    private int upperBound(int[] nums, int lef, int rig, int target) {        while (lef < rig) {            int mid = lef + (rig - lef) / 2;            if (target >= nums[mid])//不同于lowerBound()的地方                lef = mid + 1;            else                rig = mid;        }        return lef;    }    public int[] searchRange(int[] nums, int target) {        if(nums.length == 0)            return new int[]{-1, -1};        int lef = lowerBound(nums,0,nums.length - 1,target);        int rig = upperBound(nums,0,nums.length - 1,target);        if(nums[lef] != target)            return new int[]{-1, -1};        if(lef == rig)            return new int[]{lef,lef};        if(nums[rig] != target)            return new int[]{lef,rig - 1};        return new int[]{lef,rig};    }}

最后，我们需要注意一下边界的问题，如果所有元素都小于 target ，lowerBound()会返回末尾，而所有元素都小于等于 target ，upperBound()也会返回末尾，所以我们这个地方需要特判一下即可。

结果非常不错，因为两次都是利用二分查找，所以时间复杂度只有，而且不会被极端数据卡到。

总结

其实本题还是二分查找的变形，但凡是在有序的数据里面去查找，或者说，答案具有单调的性质，我们都可以尝试二分来解决。

力扣链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 720 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412