03-算法打卡-数组-二分查找-leetcode(34)-第三天

1 题目地址

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（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 <= 105 * -109 <= nums[i] <= 109 * nums 是一个非递减数组 * -109 <= target <= 109https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/

2 题目说明

给定一个按照升序排列的整数数组 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]

3 解题思路

寻找target在数组里的左右边界，有如下三种情况：
1、target在数组范围的右边或者左边，例如数组{3, 4, 5}，target为2或者target为6，此时应该返回{-1,-1}
2、target在数组范围中，且数组中不存在target，例如数组{3, 6, 7}，target为5，此时应该返回{-1,-1}
3、target在数组范围中，且数组中存在target，例如数组{3,6,7},target为6，此时应该返回{1, 1}

重点是找到等于target的左边界、右边界；
暴力解决方式：
        从前往后遍历数组找到第一个等于target的元素，即为左边界，依次遍历找到最右边的，即为右边界。

二分查找：
        将问题拆分为一个查找左边界、一个查找右边界。
        二分查找左边界，查找到第一个等于目标值：
                当target>middle，target在右区间，向右移动，left=middle+1；
                当target<middle，target在左区间，向左移动，right=middle-1；
                当target=middle，数组存在相等的情况，target在左区间，向左移动，right=middle-1
        二分查找右边界，查找到最后一个等于目标值：
                当target>middle，target在右区间，向右移动，left=middle+1；
                当target<middle，target在左区间，向左移动，right=middle-1；
                当target=middle，数组存在相等的情况，target在右区间，向右移动，left=middle+1；

4 代码编写

4.1 暴力方式

class Solution {public int[] searchRange(int[] nums, int target) {int left = -1;int right = -1;for (int i=0; i<nums.length; i++) {if (nums[i]==target) {// 左边界if (left==-1) {left = i;right = i;}// 右边界if (left!=-1) {right = i;}// 大于目标值后则跳出if (nums[i]>target) {break;}}}return new int[] {left, right};}
}

 

4.2 二分查找

找左边界发现等于target时，可能左边还有等于target，这个时候向左移动，right=middle-1
找右边界发现等于target时，可能右边还有等于target，这个时候向右移动，left=middle+1
总结：数据可能在那边就往那边移动

class Solution {public int[] searchRange(int[] nums, int target) {int left = getLeftBorder(nums, target);int right = getRightBorder(nums, target);return new int[] {left, right};}// 查找最左边界public int getLeftBorder(int[] nums, int target) {int leftBorder = -1;int left = 0;int right = nums.length - 1;while (left<=right) {int middle = (left+right)/2;if (target>nums[middle]) {left = middle + 1;} else {if (target==nums[middle]) {leftBorder = middle;}right = middle - 1;}}return leftBorder;}// 查找最右边界public int getRightBorder(int[] nums, int target) {int rightBorder = -1;int left = 0;int right = nums.length - 1;while (left<=right) {int middle = (left+right)/2;// target小于时，目标在左侧，向左移动if (target<nums[middle]) {right = middle - 1;} else {if (target==nums[middle]) {rightBorder = middle;}left = middle + 1;}}return rightBorder;}
}