济南建设厅网站安全员,网站图片优化工具,html表白网页制作源码,怎样建立网站有哪些流程34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣#xff08;LeetCode#xff09; 转化 通过题目时间复杂度为O(logN),我们就可以联想到二分算法#xff0c;但是我们前面学到的算法#xff0c;是查找出#xff0c;有序数组里的值#xff0c;并不是求其中的范围LeetCode 转化 通过题目时间复杂度为O(logN),我们就可以联想到二分算法但是我们前面学到的算法是查找出有序数组里的值并不是求其中的范围于是我们可以将找到这个值出现的范围转化为
通过二分法找到最左边下标以及最右边下标
思路
1.找到最左边下标
第一步根据mid的与target的大小进行left和right的移动如图当tmid,说明最小下标点一定在左边所以移动right , 将right赋值给mid,重新进入循环这样即可得到最左边的下标
2.细节处理
1.当right left的同时左端点就是这个点所以循环条件为left right
2.在mid范围内mid最大值比最小下标小1所以left mid1;
3.当left和right中间无元素时取中点方式的不同可能会造成死循环分析图如下 4.得到值最左边下标
具体思路图如下 2.找到最右边下标 实现思路 细节处理
由于right 在 t mid内所以在t mid内想要left 与right 相交就得right mid -1
取中间点的方法和上面找到最左边下标思路相同 注意
考虑没有target值和数组为空的情况
代码实现
class Solution {public int[] searchRange(int[] nums, int target) {int[] array {-1,-1};if(nums.length 0) return array;//找到左边界点int left 0,right nums.length-1;while(leftright){int mid left (right-left)/2;if(nums[mid] target){left mid1;}else{right mid;}}if(nums[left] ! target) return array;else{array[0] left;}//找到右边界点 left 0;right nums.length-1;while(leftright){int mid left (right-left1)/2;if(nums[mid] target){right mid-1;}else{left mid;}}if(nums[left] ! target) return array;else{array[1] right;} return array;}}
