LeetCode100之在排序数组中查找元素的第一个和最后一个位置(34)--Java

1.问题描述

给你一个按照非递减顺序排列的整数数组 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 <= 109

难度等级

中等

题目链接

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

2.解题思路

这道题最后要我们找target的第一个位置和最后一个位置，但是本质上还是找的一个target的题目。因为给我们的是一个非递减的数组，所以我们只要找到了一个target，其他target就在我们找到的target的左边或者右边。

在正式查找之前，我们可以先做一个判断，判断target不存在于数组中的一些特殊情况，比如数组本身就是空的，target小于数组的最小值和target大于数组的最大值，target都不会在数组中。

        //如果数组为空数组，直接返回//检查target是否小于nums的最小值//检查target是否大于nums的最大值if(nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]){return new int[]{-1,-1};}

接着，就是用二分查找，在给定的递增数组中找到一个target的位置，先确定左右指针和二分指针，二分循环的条件是在没有找到target值之前，左右指针不越界，就可以不断循环查找，接着就是更新二分指针，根据二分值与target的大小关系，不断缩小二分范围，直到找到target或者左右指针越界。

        //二分查找目标值int left = 0;int right = nums.length - 1;int mid = 0;while(left <= right){//更新中间值mid = (right - left) / 2 + left;//判断中间值是否等于目标值if(nums[mid] == target){break;}//中间值小于目标值if(nums[mid]  < target){left = mid + 1;}//中间值大于目标值if(nums[mid] > target){right = mid - 1;}}

我们推出二分循环后，存在两种情况，一种是左右指针越界，说明我们在数组中没有找到target，返回两个-1；另一种情况是我们找到了一个target，这种情况，我们接着往下分析。

        //根据查找结果，判断第一个目标值和最后一个目标值的位置//因为左右指针越界而结束查找if(left > right){return new int[]{-1,-1};}

我们既然已经找到了一个target，那么其余的target就在我们找到的这个target左边或者右边，求第一个位置的索引，我们就往左边找，求最后一个位置的索引，我们就往右边找，找的时候，记得不要让指针越界即可。

        //找到了目标值int first = mid;int last = mid;//向前寻找第一个位置while(first >= 0 && nums[first] == target){first--;}//因为找到的是不等于target的位置，要+1恢复到等于target的位置if(first < nums.length - 1){first++;}//向后寻找最后一个位置while(last < nums.length && nums[last] == target){last++;}//因为找到的是不等于target的位置，要-1恢复到等于target的位置if(last > 0){last--;}

找到第一个位置的索引和最后一个位置的索引之后，将两个索引一起返回就好了。

3.代码展示

class Solution {public int[] searchRange(int[] nums, int target) {//如果数组为空数组，直接返回//检查target是否小于nums的最小值//检查target是否大于nums的最大值if(nums.length == 0 || target < nums[0] || target > nums[nums.length - 1]){return new int[]{-1,-1};}//二分查找目标值int left = 0;int right = nums.length - 1;int mid = 0;while(left <= right){//更新中间值mid = (right - left) / 2 + left;//判断中间值是否等于目标值if(nums[mid] == target){break;}//中间值小于目标值if(nums[mid]  < target){left = mid + 1;}//中间值大于目标值if(nums[mid] > target){right = mid - 1;}}//根据查找结果，判断第一个目标值和最后一个目标值的位置//因为左右指针越界而结束查找if(left > right){return new int[]{-1,-1};}//找到了目标值int first = mid;int last = mid;//向前寻找第一个位置while(first >= 0 && nums[first] == target){first--;}//因为找到的是不等于target的位置，要+1恢复到等于target的位置if(first < nums.length - 1){first++;}//向后寻找最后一个位置while(last < nums.length && nums[last] == target){last++;}//因为找到的是不等于target的位置，要-1恢复到等于target的位置if(last > 0){last--;}return new int[]{first,last};}
}