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

原题链接：leetcode34

for循环查找

class Solution {public int[] searchRange(int[] nums, int target) {int a=-1,b=-1;for(int i=0;i<nums.length;i++){if(nums[i]==target){a=i;break;}}for(int j=nums.length-1;j>=0;j--){if(nums[j]==target){b=j;break;}}return new int[]{a,b};}
}

初始化变量

a和b分别用于存储目标值target在数组中的起始位置和结束位置。设为-1，如果目标值不存在于数组中，就返回[-1,-1]

查找位置

分别用两个for循环遍历查找起始和结束位置，找到后用变量记录位置并立即结束循环

时间复杂度O(n)
空间复杂度O(1)

二分查找法

class Solution {public int[] searchRange(int[] nums, int target) {int first = findFirst(nums, target);if (first == -1) {return new int[]{-1, -1}; // 如果没有找到目标值，直接返回 [-1, -1]}int last = findLast(nums, target);return new int[]{first, last};}private int findFirst(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {if (mid == 0 || nums[mid - 1] != target) {return mid; // 找到了第一个目标值}right = mid - 1;}}return -1;}private int findLast(int[] nums, int target) {int left = 0, right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;} else if (nums[mid] > target) {right = mid - 1;} else {if (mid == nums.length - 1 || nums[mid + 1] != target) {return mid; // 找到了最后一个目标值}left = mid + 1;}}return -1;}
}

代码结构

主方法 searchRange：调用两个辅助方法 findFirst 和 findLast 来分别找到目标值的第一次出现和最后一次出现的位置。
辅助方法 findFirst：用于找到目标值第一次出现的位置。
辅助方法 findLast：用于找到目标值最后一次出现的位置。

主方法 `searchRange`

首先调用 findFirst 方法尝试找到目标值的起始位置。
如果 findFirst 返回 -1，说明目标值不在数组中，直接返回 [-1, -1]。
否则，调用 findLast 方法找到目标值的结束位置，并将起始和结束位置作为一个数组返回。

辅助方法 `findFirst`

初始化 left 和 right 指针，分别指向数组的开始和结束。
使用一个循环来进行二分查找。每次迭代时，计算中间索引 mid。
如果 nums[mid] 小于 target，说明目标值在右半部分，更新 left 指针。
如果 nums[mid] 大于 target，说明目标值在左半部分，更新 right 指针。
如果 nums[mid] 等于 target，检查是否是第一个目标值：
- 如果 mid 是 0 或者 nums[mid - 1] 不等于 target，说明找到了第一个目标值，返回 mid。
- 否则，继续在左半部分查找，更新 right 指针。
如果循环结束后没有找到目标值，返回 -1。

辅助方法 `findLast`

这个方法与 findFirst 类似，但它是用来找到目标值的最后一次出现的位置。
当 nums[mid] 等于 target 时，检查是否是最后一个目标值：
- 如果 mid 是数组的最后一个元素或者 nums[mid + 1] 不等于 target，说明找到了最后一个目标值，返回 mid。
- 否则，继续在右半部分查找，更新 left 指针。