从零学算法34

34.给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

• 非递减数组求区间，很容易想到的是两次二分查找找到左右边界。由于左右边界的找法几乎相同，所以把题目转换一下，只要找到 target 的右边界，我们就知道了结束位置为右边界 - 1；而开始位置，我们只要知道 target - 1 的右边界即可，因为是整数数组，所以只要 target 在数组中存在，那么刚刚大于 target - 1（也就是右边界） 的肯定是 target。这样的话我们只需要把二分查找右边界写成方法，最终返回大致为 [solve(target-1),solve(target)-1] 即可。剩下的就是分析区间不存在的情况。首先数组没数肯定就直接返回了，其次如果我能找到区间。那么可以肯定的是，nums[开始位置] 一定是等于 target 的，不是的话肯定也返回了。还有就是如果所有数都比 target 小，那么起始位置会找到数组外面去，所以二分查找返回的数组下标也应当合法。

•   public int[] searchRange(int[] nums, int target) {if(nums.length == 0){return new int[]{-1,-1};}int first = solve(nums,target-1);// 需要先判断 first 是否合法，否则 nums[first] 可能直接数组越界了if(first >= nums.length || nums[first] != target){return new int[]{-1,-1};}return new int[]{first,solve(nums,target)-1};}public int solve(int[] nums,int target){int left=0,right=nums.length-1;while(left<=right && left >=0 && right <= nums.length-1){int mid = (left+right)/2;// 这里用小于等于，那么左边界就会不断右移，直到找到大于 target 的第一个数// 所以这里的 left 最后就是 target 的右边界，如果用小于就是左边界了if(nums[mid]<=target)left=mid+1;else right=mid-1;}return left;}