今日感受： (ง •_•)ง
题目描述：
LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8 输出：[3,4]
解题代码：
class Solution {
public static int FindFirstIndex(int[] nums, int target){
int l = 0, r = nums.length -1;
while(l < r){
int midIndex = (l+r)/2;
// 更新边界
if(nums[midIndex] >= target){
r = midIndex;
}else if(nums[midIndex] < target){
l = midIndex + 1;
}
}
if (nums[r] == target){
return r;
}
return -1;
}
public static int FindLastIndex(int[] nums, int target){
int l = 0, r = nums.length -1;
while(l < r){
int midIndex = (l+r+1)/2;
System.out.println(midIndex);
// 更新边界
if(target >= nums[midIndex]){
l = midIndex; // l = midIndex 需要 midIndex = (l+r+1)/2 (加1的目的向上取正)
}else{
r = midIndex-1;
}
}
if (nums[r] == target){
return r;
}
return -1;
}
public int[] searchRange(int[] nums, int target) {
int [] res = new int[2];
if(nums.length == 0){
res[0] = -1;
res[1] = -1;
return res;
}
res[0] = Solution.FindFirstIndex(nums,target);
res[1] = Solution.FindLastIndex(nums,target);
return res;
}
}
提交结果：
解题思路：
要求时间复杂度为O(log n)，则采用二分法。
（1）采用两个二分法
FindFirstIndex(int[] nums, int target) ： 第一个二分找第一个target的index。
FindLastIndex(int[] nums, int target) ： 第二个二分找倒数第一个target的index。
（2）虽然本质都是使用二分法进行搜索，但是一定要注意边界更新问题以及midIndex取值问题
（3） FindFirstIndex(int[] nums, int target) 方法： 第一个二分找第一个target的index。
1. 确定边界 l = 0, r = nums.length -1;
2. 确定循环遍历条件 while(l < r) ： l == r 的时候跳出循环（找到唯一点）
3. midIndex = (l+r)/2
4. 确定更新边界条件：（往左逼近）
nums[midIndex] >= target 更新 r = midIndex;
【注意：条件是 >= ，保证即使连续几个相同的target值在数组内，确保边界更新向最前移动并最终指向的是第一个】
nums[midIndex] < target 更新 l = midIndex + 1; （闭区间取所有可能的值）
5. 结束循环之后判断当前找到的值是否与target值相同，是则返回 r 边界（即第一个target的Index值），否则返回-1.
（4） FindLastIndex(int[] nums, int target) 方法：第二个二分找倒数第一个target的index。
1. 确定边界 l = 0, r = nums.length -1;
2. 确定循环遍历条件 while(l < r) ： l == r 的时候跳出循环（找到唯一点）
3. 注意此时的 midIndex = (l+r+1)/2 而不是 midIndex = (l+r)/2
原因：由于除法是向下取整，所以midIndex = (l+r)/2 向下取整，刚好符合向左逼近。然而此时寻找最后一个是向右逼近，所以需要向上取整 midIndex = (l+r+1)/2 （此时加1实现向上取整）。如果不加1的话，无法跳出循环，midIndex 始终为数组倒数第二个Index值（因为不加1，除法就是向下取整，最后一个Index值取不到）。
4. 确定更新边界条件：（往右逼近）
nums[midIndex] <= target 更新 l = midIndex;
【注意：条件是 <= ，保证即使连续几个相同的target值在数组内，确保边界更新向最后移动并最终指向的是最后一个】
nums[midIndex] > target 更新 r = midIndex-1; （闭区间取所有可能的值）。
5. 结束循环之后判断当前找到的值是否与target值相同，是则返回 r 边界（即第一个target的Index值），否则返回-1.
（5）在searchRange方法中
1. 首先判断nums是否为空 （一定注意）
2. 通过类名直接调用定义的静态方法FindFirstIndex和FindLastIndex
res[0] = Solution.FindFirstIndex(nums,target);
res[1] = Solution.FindLastIndex(nums,target);
然后 return res 。
