文章目录
- 1. 题目链接
- 2. 题目大意
- 3. 示例
- 4. 解题思路
- 参考代码
1. 题目链接
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)
2. 题目大意
描述:给你一个按照非递减顺序排列的整数数组 nums
,和一个目标值 target
。
要求:找出给定目标值在数组中的开始位置和结束位置。
说明:
- 要求使用时间复杂度为 O(logn) 的算法解决问题。
3. 示例
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]
4. 解题思路
要求使用时间复杂度为 O(logn) 的算法解决问题,那么就需要使用「二分查找算法」了。
- 进行两次二分查找,第一次尽量向左搜索。第二次尽量向右搜索。
参考代码
class Solution {public int[] searchRange(int[] nums, int target) {int start = lowerBound(nums, target);if (start == nums.length || nums[start] != target) {return new int[]{-1, -1}; // nums 中没有 target}// 如果 start 存在,那么 end 必定存在int end = lowerBound(nums, target + 1) - 1;return new int[]{start, end};}// lowerBound 返回最小的满足 nums[i] >= target 的 i// 如果数组为空,或者所有数都 < target,则返回 nums.length// 要求 nums 是非递减的,即 nums[i] <= nums[i + 1]private int lowerBound(int[] nums, int target) {int left = 0, right = nums.length - 1; // 闭区间 [left, right]while (left <= right) { // 区间不为空// 循环不变量:// nums[left-1] < target// nums[right+1] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1; // 范围缩小到 [mid+1, right]} else {right = mid - 1; // 范围缩小到 [left, mid-1]}}return left;}
}