behance网站_黑龙江省建设厅官网_线下推广渠道和方式_推广软文发稿

1. 题目链接

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

---

2. 题目大意

描述：给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。

要求：找出给定目标值在数组中的开始位置和结束位置。

说明：

• 要求使用时间复杂度为 O(log⁡n) 的算法解决问题。

---

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(log⁡n) 的算法解决问题，那么就需要使用「二分查找算法」了。

• 进行两次二分查找，第一次尽量向左搜索。第二次尽量向右搜索。

---

参考代码

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;}
}

---