34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣(LeetCode)
转化
通过题目时间复杂度为O(logN),我们就可以联想到二分算法,但是我们前面学到的算法,是查找出,有序数组里的值,并不是求其中的范围,于是我们可以将找到这个值出现的范围转化为
通过二分法找到最左边下标以及最右边下标
思路:
1.找到最左边下标
第一步:根据mid的与target的大小进行left和right的移动,如图,当t<=mid,说明最小下标点一定在左边,所以移动right , 将right赋值给mid,重新进入循环,这样即可得到最左边的下标
2.细节处理
1.当right == left的同时,左端点就是这个点,所以循环条件为left < right
2.在mid范围内mid最大值比最小下标小1,所以left = mid+1;
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(left<right){int mid = left +(right-left)/2;if(nums[mid] < target){left = mid+1;}else{right = mid;}}if(nums[left] != target) return array;else{array[0] = left;}//找到右边界点 left = 0;right = nums.length-1;while(left<right){int mid = left +(right-left+1)/2;if(nums[mid] > target){right = mid-1;}else{left = mid;}}if(nums[left] != target) return array;else{array[1] = right;} return array;}}