LeetCode 34.在排序数组中查找元素的第一个和最后一个位置题目链接:
题目描述:
给定一个按照升序排列的整数数组
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]
提示：
-
0 <= nums.length <=
10
5
10^{5}
1
0
5
-
–
10
9
10^{9}
1
0
9
<= nums[i] <=
10
9
10^{9}
1
0
9
- nums 是一个非递减数组
-
–
10
9
10^{9}
1
0
9
<= target <=
10
9
10^{9}
1
0
9
题目分析:
这道题我们通过二分查找的方法解决。首先我们要定义两个方法，一个是用二分查找法寻找元素第一次出现的位置，另一个是用二分查找法寻找元素最后一次出现的位置。下面讲一下寻找第一次出现元素位置的方法，定义左边界为0，右边界为数组长度，当左边界小于右边界时执行二分查找，先找出区间中点值，并与目标值比较，如果目标值与中点值相同或者目标值小于中点值，缩小范围至左子区间，否则缩小范围至右子区间。如果左边界到达数组尾或者左边界值移动到最后还找不到与目标相同的值则返回-1，否则返回元素第一次出现的位置。同理我们可以写出寻找最后一次出现元素位置的方法，最后调用这两个方法获取位置值返回即可。
题解:
执行用时: 0 ms
内存消耗: 41.2 MB
class Solution {
public int[] searchRange(int[] nums, int target) {
// 调用方法 实现返回 第一次元素出现位置 和 最后一次元素出现位置
return new int[]{findLeft(nums, target), findRight(nums, target)};
}
// 寻找第一次出现元素位置的方法
public int findLeft(int[] nums, int target) {
// 定义左右边界
int left = 0, right = nums.length;
// 当左边界小于右边界时执行循环
while (left < right) {
// 定义区间中点
int mid = left + (right - left) / 2;
// 如果目标值与中点值相同或者目标值小于中点值，缩小范围至左子区间
if (target <= nums[mid])
// 移动右边界界线
right = mid;
// 如果目标值大于中点值，缩小范围至右子区间
else if (target > nums[mid])
// 移动左边界界线
left = mid + 1;
}
// 如果左边界到达数组尾 或者 左边界值移动到最后还找不到与目标相同的值
if (left == nums.length || nums[left] != target)
// 则返回-1
return -1;
// 返回元素第一次出现的位置
return left;
}
// 寻找最后一次出现元素位置的方法
public int findRight(int[] nums, int target) {
// 定义左右边界
int left = 0, right = nums.length;
// 当左边界小于右边界时执行循环
while (left < right) {
// 定义区间中点
int mid = left + (right - left) / 2;
// 如果目标值与中点值相同或者目标值大于中点值，缩小范围至右子区间
if (target >= nums[mid])
// 移动左边界界线
left = mid + 1;
// 如果目标值小于中点值，缩小范围至左子区间
else if (target < nums[mid])
// 移动右边界界线
right = mid;
}
// 如果右边界到达数组头 或者 右边界值移动到最后还找不到与目标相同的值
if (right == 0 || nums[right - 1] != target)
// 则返回-1
return -1;
// 返回元素最后一次出现的位置
return right - 1;
}
}
题目来源:力扣(LeetCode)