34. 在排序数组中查找元素的第一个和最后一个位置
难度中等597收藏分享切换为英文关注反馈
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]通过次数134,913
提交次数334,126
题解
class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[]{getFrist(nums,target), getLast(nums,target)};
}
public static int getFrist(int[] nums, int target){
int l = 0;
int r = nums.length;
while(l < r){
int mid = l + (r-l)/2;
if( nums[mid] == target){
r = mid;
}else if( nums[mid] > target){
r = mid;
}else{
l = mid+1;
}
}
if( l == nums.length) return -1;
if( nums[l] ==target) return l;
return -1;
}
public static int getLast(int[] nums, int target){
int l = 0;
int r = nums.length;
while(l < r){
int mid = l + (r-l)/2;
if( nums[mid] == target){
l = mid+1;
}else if( nums[mid] > target){
r = mid;
}else{
l = mid+1;
}
}
if(r == 0) return -1;
if(nums[r - 1] ==target) return r-1;
return -1;
}
}模板
int left = 0;
int right = num.length;
while(left < right){
int mid = left + (right - left)/2;
if(nums[mid] < target){
left = mid+1;
}else{
right = mid
}
}
return left;参考
如果不要求时间复杂度，只需要分别正序遍历找左边target和逆序遍历找右边target即可。但是根据题目要求的时间复杂度O(log n)，看出这依然是一个二分查找的变种。
思路一：二分法再线性法
二分法找到target，如果不存在则返回[-1,-1]。
如果nums[mid]==target，利用数组有序的特点， 以mid为中心分别向左向右线性查找，找到最左和最右的target值。
public int[] searchRange(int[] nums, int target) {
int[] result={-1,-1};
int left=0,right=nums.length-1;
//先二分法找到target的下标
while (left<=right){
int mid=(left+right)/2;
//如果找到target的下标mid，就以mid为中心分别向左向右线性查找
if (nums[mid]==target){
int left_key=mid,right_key=mid;
//向左向右线性查找，直至找到不等于target
while (left_key>=0&&nums[left_key]==target)left_key--;
while (right_key<nums.length&&nums[right_key]==target)right_key++;
//保存最左和最右的target值的下标
result[0]=left_key+1;
result[1]=right_key-1;
//终止二分法
break;
}else if (nums[mid]<target){
left=mid+1;
}else if (nums[mid]>target){
right=mid-1;
}
}
return result;
}
最坏情况，有序数组中元素都等于target，例如target=8，[8,8,8,8,8,8]，则线性寻找最左最右时需要遍历每个元素。所以时间复杂度是：O(n)。但是因为测试数据的关系，leetcode中这种思路也是可以通过的。
思路二：直接二分法分别查找
嘴笨，说的比较抽象，其实根据下述方法，动笔在纸上画一画模拟一下就很清晰明了了。
二分法查找最左target：如果中间值(nums[mid])不等于target，则根据情况移动left或者right来减半搜索区间范围即可。需要改变的是：当中间值等于target，不能直接返回，而是要收缩right减小搜索区间继续逐步锁定最左的target。
最终得到的left(因为循环终止条件时right==left，所以最终left和right是相等的)可以理解成：数组中比target小的元素的个数。所以最终进行简单的判断即可，如果left==nums.length说明所有的数都比target小则返回-1，如果nums[left]==target则nums[left]就是最左的target，否则数组中没有target返回-1。
二分法查找最右target：如果中间值(nums[mid])不等于target，则根据情况移动left或者right来减半搜索区间范围即可。需要改变的是：当中间值等于target，不能直接返回，而是要增加left减小搜索区间继续逐步锁定最右的target。
因为搜索区间是[0，nums.length)为左闭右开，所以最后判断和返回时需要对left或者right减一，防止越界。这个”减一”也可以这么理解：’if (nums[mid]==target)left=mid+1;’当while循环结束的时候nums[left]的值一定不是target，但是nums[left-1]的值有可能是，所以返回‘nums[right-1]==target?right-1:-1’即可。
public int[] searchRange(int[] nums, int target) {
int[] result={-1,-1};
result[0]=searchLeft(nums,target);
result[1]=searchRight(nums,target);
return result;
}
//查找最左target
public int searchLeft(int[] nums,int target){
int left=0,right=nums.length;
//这里是<而不是<=，因为搜索区间是[0，length)，终止条件是left==right
while (left<right){
int mid =(left+right)/2;
//因为是寻找最左target，所以这里不能直接返回，而是收缩right去锁定左侧边界
if (nums[mid]==target){
right=mid;
}else if (nums[mid]<target){
left=mid+1;
}else if (nums[mid]>target){
//这里是=mid而不是=mid-1，因为搜索区间是左闭右开
right=mid;
}
}
//如果target比所有数都大，则返回-1
if (left==nums.length)return -1;
//终止条件是left==right，所以返回left或者right都可
return nums[left]==target?left:-1;
}
//寻找最右target
public int searchRight(int[] nums,int target){
int left=0,right=nums.length;
//这里是<而不是<=，因为搜索区间是[0，length)
while (left<right){
int mid=(left+right)/2;
//因为是寻找最右target，所以不能直接返回，而是要增大left去锁定左侧边界
if (nums[mid]==target){
left=mid+1;
}else if (nums[mid]>target){
right=mid;
}else if (nums[mid]<target){
left=mid+1;
}
}
if (right==0)return -1;
//由于每次收紧左侧边界都是left=mid+1（因为搜索区间是左闭右开），所以无论是left还是right都需要-1
return nums[right-1]==target?right-1:-1;
}时间复杂度：O(log n)
注意事项：
二分法中比较麻烦容易出错的点就是搜索区间的确定，因为这会影响到循环条件和搜索区间端点(left和right)的移动。
思路一中：left=0，right=length-1所以搜索区间是[0，length-1]左闭右闭的，所以循环终止的条件是left>right即while(left<=right)，区间端点移动时因为mid不是需要的值所以排除，即left=mid+1，right=mid-1排除了mid并且新的搜索区间是[0，mid-1]或者[mid+1，lenght-1]依然是左闭右闭。
思路二中：left=0，right=length所以搜索区间是[0，length)左闭右开的，所以循环终止的条件是left==right所以while(left<right)即可，区间端点移动时因为mid不是需要的值所以排除，即left=mid+1，right=mid排除了mid并且新的搜索区间是[0，mid)或者[mid+1，lenght)依然是左闭右闭。
作者：jerrymouse1998
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-fa-de-liang-chong-bian-xing-fang-shi-by-da-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
debug
public class test {
public static void main(String[] args) {
int[] nums = new int[]{5,7,7,8,8,10};
int target = 11;
int l = 0;
int r = nums.length;
while(l < r){
int mid = l + (r-l)/2;
if( nums[mid] == target){
r = mid;
}else if( nums[mid] > target){
r = mid;
}else{
l = mid+1;
}
}
if( l == nums.length) System.out.println("l为"+l+"nums.length为"+nums.length);
if( nums[l] ==target) System.out.println("l为"+l);;
}输入为
l为6 nums.length为6转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 mym_74@163.com