题目描述
给你一个按照非递减顺序排列的整数数组 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^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= -0^9
一、思路
题中提到"有序"和“规定的时间复杂度O(log n)“，我们就应该要想到使用二分法来进行题解，但是二分法每次求出一个值，无法返回一个范围，所以我们可以通过使用两次二分法来分别获得目标值的左边边界值和右边边界值。
求左边边界值：判断标准，是左边没有目标值等价于左边的数小于目标值和左边没有值 即：
// 这里是主要判断：如果左边界是第一个或者前一个数小于左边界m // 即可证明m左边没有和m相同的数了，否则将right向左移 if(nums[mid] == target){ if(mid ==0 || nums[mid-1]<target){ return mid; } right = mid-1; }
求右边边界值：判断标准，是右边没有目标值等价于右边的数大于目标值和右边没有值
// 这里是主要判断：如果右边界是最后一个或者后面一个数大于右边界n // 即可证明n右边没有和n相同的数了，否则将left向右移 if(nums[mid] == target){ if(mid ==nums.length-1 || nums[mid+1]>target){ return mid; } left = mid+1; }
二、参考代码
完整代码：
class Solution { // 二分查找每次只能找到一个，所以可以通过两次二分查找来找到目标值左边界和右边界，最后返回 public int[] searchRange(int[] nums, int target) { int left = searchLeft(nums,target); int right = searchRight(nums,target); if(left == -1 && right == -1){ return new int []{-1,-1}; } return new int[]{left,right}; } // 寻找目标值左边界m public int searchLeft(int[]nums,int target){ int left = 0,right=nums.length-1; while(left<=right){ int mid = left+((right-left)>>1); // 这里是主要判断：如果左边界是第一个或者前一个数小于左边界m // 即可证明m左边没有和m相同的数了，否则将right向左移 if(nums[mid] == target){ if(mid ==0 || nums[mid-1]<target){ return mid; } right = mid-1; } if(nums[mid]>target){ right = mid-1; } if(nums[mid]<target){ left= mid+1; } } return -1; } // 寻找目标值右边界n public int searchRight(int[]nums,int target){ int left = 0,right=nums.length-1; while(left<=right){ int mid = left+((right-left)>>1); // 这里是主要判断：如果右边界是最后一个或者后面一个数大于右边界n // 即可证明n右边没有和n相同的数了，否则将left向右移 if(nums[mid] == target){ if(mid ==nums.length-1 || nums[mid+1]>target){ return mid; } left = mid+1; } if(nums[mid]>target){ right = mid-1; } if(nums[mid]<target){ left= mid+1; } } return -1; } }
![[leetcode~dfs]1261. 在受污染的二叉树中查找元素](https://ucc.alicdn.com/pic/developer-ecology/okfcmqqjwxoec_335a965e888346009ec98ec28a431196.png?x-oss-process=image/resize,h_160,m_lfit)