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

简介题目链接https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/解决方式数组 二分查找这是作者学习众多大神的思路进行解题的步骤很推荐大家解题的时候去看看题解里面大佬们的思路、想法二分查找思路这题是704二分查找题目的进一步涉及到左右边界问题。在二分查找的基础上找到目标元素不返回而是进一步收缩区间范围找到左右边界。这题做了个转换并不是找到左边界之后修改算法直接找右边界而是将目标元素 1复用查找左边界的二分算法找比目标元素大一点元素的左边界找到后该左边界 - 1 就是目标元素的右边界了。具体可参考labuladong704、灵茶山艾府大佬关于二分查找一系列的详细题解classSolution{publicint[]searchRange(int[]nums,inttarget){// 边界处理if(nums.length0){returnnewint[]{-1,-1};}// 二分查找intfirstleft(nums,target);// 有几种情况// 一种目标元素比所有元素都大left nums.length// 一种目标元素在数组范围中但不存在目标元素nums[first] ! targetif(firstnums.length||nums[first]!target){returnnewint[]{-1,-1};}// 复用二分查找使 target 1寻找比目标元素大一点的元素的左边界其 -1 即目标元素的右边界intsecondleft(nums,target1)-1;// 进行到这一步必定找的到所以直接返回结果returnnewint[]{first,second};}// 二分函数privateintleft(int[]nums,inttarget){intleft0;intrightnums.length-1;intmid0;// 左右闭合区间while(leftright){midleft(right-left)/2;if(nums[mid]target){// 目标在右侧leftmid1;}elseif(nums[mid]target){// 目标在左侧rightmid-1;}else{// 正中目标找左边界rightmid-1;}}// 返回左边界returnleft;}}优化思路上面复用二分查找的时候直接传递了整个数组其实不用因为比目标元素大一的元素一定在右侧所以我们只需要查询右侧的数组元素就好。classSolution{publicint[]searchRange(int[]nums,inttarget){// 边界处理if(nums.length0){returnnewint[]{-1,-1};}// 二分查找intfirstleft(nums,target,0,nums.length-1);// 有几种情况// 一种目标元素比所有元素都大left nums.length// 一种目标元素在数组范围中但不存在目标元素nums[first] ! targetif(firstnums.length||nums[first]!target){returnnewint[]{-1,-1};}// 复用二分查找使 target 1寻找比目标元素大一点的元素的左边界其 -1 即目标元素的右边界// 优化缩小数组范围intsecondleft(nums,target1,first1,nums.length-1)-1;// 进行到这一步必定找的到所以直接返回结果returnnewint[]{first,second};}// 二分函数privateintleft(int[]nums,inttarget,intleftBound,intrightBound){intleftleftBound;intrightrightBound;intmid0;// 左右闭合区间while(leftright){midleft(right-left)/2;if(nums[mid]target){// 目标在右侧leftmid1;}elseif(nums[mid]target){// 目标在左侧rightmid-1;}else{// 正中目标找左边界rightmid-1;}}// 返回左边界returnleft;}}