从零学算法34-Toy模板网

这篇具有很好参考价值的文章主要介绍了从零学算法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]文章来源地址https://www.toymoban.com/news/detail-643570.html

非递减数组求区间，很容易想到的是两次二分查找找到左右边界。由于左右边界的找法几乎相同，所以把题目转换一下，只要找到 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;
  }