刷题之Leetcode34题(超级详细)

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

力扣链接(opens new window)https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

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

思路

这道题目如果基础不是很好，不建议大家看简短的代码，简短的代码隐藏了太多逻辑，结果就是稀里糊涂把题AC了，但是没有想清楚具体细节！

对二分还不了解的兄弟先做这两题：

• 704.二分查找(opens new window)https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html
• 35.搜索插入位置(opens new window)https://programmercarl.com/0035.%E6%90%9C%E7%B4%A2%E6%8F%92%E5%85%A5%E4%BD%8D%E7%BD%AE.html

下面我来把所有情况都讨论一下。

寻找target在数组里的左右边界，有如下三种情况：

• 情况一：target 在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者数组{3, 4, 5},target为6，此时应该返回{-1, -1}
• 情况二：target 在数组范围中，且数组中不存在target，例如数组{3,6,7},target为5，此时应该返回{-1, -1}
• 情况三：target 在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

这三种情况都考虑到，说明就想的很清楚了。

接下来，在去寻找左边界，和右边界了。

采用二分法来去寻找左右边界，为了让代码清晰，我分别写两个二分来寻找左边界和右边界。

刚刚接触二分搜索的兄弟不建议上来就想用一个二分来查找左右边界，很容易把自己绕进去，建议扎扎实实的写两个二分分别找左边界和右边界

寻找右边界

先来寻找右边界，至于二分查找，如果看过刷题之Leetcode704题(超级详细)-CSDN博客就会知道，二分查找中什么时候用while (left <= right)，有什么时候用while (left < right)，其实只要清楚循环不变量，很容易区分两种写法。

那么这里我采用while (left <= right)的写法，区间定义为[left, right]，即左闭右闭的区间（如果这里有点看不懂了，强烈建议把刷题之Leetcode704题(超级详细)-CSDN博客这篇文章先看了，704题目做了之后再做这道题目就好很多了）

确定好：计算出来的右边界是不包含target的右边界，左边界同理。

可以写出如下代码

 int getRightBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle]==target) {// 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;} else if(nums[middle]>target){ right = middle - 1;}else{left=middle-1;
}}return rightBorder;}

寻找左边界

 int getLeftBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] == target) { // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else if(nums[middle]>target){right=middle-1;}else{ left=middle+1;
}}return leftBorder;}

处理三种情况

左右边界计算完之后，看一下主体代码，这里把上面讨论的三种情况，都覆盖了

class Solution {int[] searchRange(int[] nums, int target) {int leftBorder = getLeftBorder(nums, target);int rightBorder = getRightBorder(nums, target);// 情况一if (leftBorder == -2 || rightBorder == -2) return new int[]{-1, -1};// 情况三if (rightBorder - leftBorder > 1) return new int[]{leftBorder + 1, rightBorder - 1};// 情况二return new int[]{-1, -1};}int getRightBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle]==target) {// 寻找右边界，nums[middle] == target的时候更新leftleft = middle + 1;rightBorder = left;} else if(nums[middle]>target){ right = middle - 1;}else{left=middle+1;
}}return rightBorder;}int getLeftBorder(int[] nums, int target) {int left = 0;int right = nums.length - 1;int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况while (left <= right) {int middle = left + ((right - left) / 2);if (nums[middle] == target) { // 寻找左边界，nums[middle] == target的时候更新rightright = middle - 1;leftBorder = right;} else if(nums[middle]>target){right=middle-1;}else{ left=middle+1;
}}return leftBorder;}

这份代码在简洁性很有大的优化空间，例如把寻找左右区间函数合并一起。

但拆开更清晰一些，而且把三种情况以及对应的处理逻辑完整的展现出来了。

总结

初学者建议大家一块一块的去分拆这道题目，正如本题解描述，想清楚三种情况之后，先专注于寻找右区间，然后专注于寻找左区间，左右根据左右区间做最后判断。

不要上来就想如果一起寻找左右区间，搞着搞着就会顾此失彼，绕进去拔不出来了。