在排序数组中查找元素的第一个和最后一个位置(力扣)

一.题目介绍

二.题目解析

使用二分进行查找

2.1处理边界情况

如果数组为空，直接返回 [-1, -1]，因为无法找到目标值。

int[] ret = new int[2];
ret[0] = ret[1] = -1;
if (nums.length == 0) return ret;

2.2查找左端点（目标值开始位置）

1.初始化指针：

• left 指向数组的起始位置（索引 0）。
• right 指向数组的结束位置（索引 nums.length - 1）。

2.二分查找：

• 计算中间位置 mid = left + (right - left) / 2 （细节一，不然可能陷入死循环）
• 如果 nums[mid] < target，说明目标值在右半部分，更新 left = mid + 1。
• 如果 nums[mid] >= target，说明目标值在左半部分或当前位置就是目标值，更新 right = mid。

 

3.循环退出并判断：

• 当循环条件是left<right 进行判断，不能是left<=right（细节二，不然可能会陷入死循环）
• 当 left == right 时，循环结束，此时 left 或 right 指向目标值的第一个位置（如果存在）
• 如果 nums[right] != target，说明目标值不存在，直接返回 [-1, -1]，否则设置ret[ 0 ] = left,保存开始位置。
   

细节一解析：

求中间位置有两种：

mid = left + (right - left) / 2（数组长度是奇数则在中间位置，偶数长度在中间位置偏左）

mid = left + (right - left + 1) / 2（数组长度是奇数则在中间位置，偶数长度在中间位置偏右）

如果使用left + (right - left + 1) / 2可能会陷入死循环

如果剩下两个数字，mid值大于目标值时，需要更新right = mid位置，相当于没移动，循环判断依旧如此，陷入死循环。

---

细节二解析：

为什么循环判断条件不能是 left <= right？,一张图解释

当left == right时，还要继续进入循环，还是更新right = mid，不移动，如此循环判断，陷入死循环。

视频展示：

 

 2.3查找右端点（目标值结束位置）

 

1.重新初始化指针：

• left 指向数组的起始位置（索引 0）。
• right 指向数组的结束位置（索引 nums.length - 1）。

 

2.二分查找：

• 计算中间位置 mid = left + (right - left + 1) / 2。（细节一，避免陷入死循环）
• 如果 nums[mid] <= target，说明目标值在右半部分或当前位置就是目标值，更新 left = mid。
• 如果 nums[mid] > target，说明目标值在左半部分，更新 right = mid - 1。

 

3.循环退出并判断：

• 当循环条件是left<right 进行判断，不能是left<=right（细节二，不然可能会陷入死循环）
• 当 left == right 时，循环结束，此时 left 或 right 指向目标值的最后一个位置（如果存在）。
• 将 ret[1] 设置为 left，即目标值的结束位置。

细节一解析

如果使用left + (right - left ) / 2可能会陷入死循环

如果剩下两个数字，mid值小于等于目标值时，需要更新left= mid位置，相当于没移动，循环判断依旧如此，陷入死循环。

---

细节二跟求左端点一致。

 视频展示：

 

三.题目源码

class Solution {public int[] searchRange(int[] nums, int target) {//判断边界情况int[]  ret = new int[2];ret[0] = ret [1] = -1;if(nums.length == 0) return ret;//求左端点int left = 0; int right = nums.length - 1;while(left < right){int mid = left + (right - left ) / 2;if(nums[mid] < target) left = mid + 1;else right = mid ;}if(nums[right] != target) return ret;else ret[0] = right;//求右端点left = 0;right = nums.length -1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] <= target) left = mid;else right = mid - 1;}ret[1] = left;return ret;}
}