Java每日刷题之二分算法

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;}}