leetCode 034 在排序数组中查找第一个和最后一个元素

题目描述：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例输入输出：

  1. 输入：nums = [5,7,7,8,8,10], target = 8
  2. 输出：[3,4]
  4. 输入：nums = [5,7,7,8,8,10], target = 6
  5. 输出：[-1,-1]
  7. 输入：nums = [], target = 0
  8. 输出：[-1,-1]

思路：

两次二分

  • 第一次使用二分法将最左边的target位置找出来，第二次使用二分法将最右边的target位置找出来

  • 参数：

    • 左指针left，右指针right，返回的数组result。

  • 流程：

    • 判断是否要查找：

      • 如果数组长度为0或者数组不存在，直接返回{-1，-1}

    • 第一次二分：查找最左边的target。

      • 如果nums[mid] < target , left = mid +1；
      • 否则，right = mid
      • 为了不让right == target的时候停止才如此设置。
    • 如果left == right 的时候，nums[left] 的值不为target，则没有此元素，直接返回{-1,-1}

    • 第二次二分：查找最右边的target。

      • 如果nums[mid] 大于target， right = mid
      • 否则 left = mid
    • 将right 赋值给result[1]
    • 返回result

  • 复杂度分析：

    • 时间复杂度：二分两次，O(log n)
    • 空间复杂度：O（1）

  • 代码：

  • class Solution {
  public int[] searchRange(int[] nums, int target) {

      int left = 0, right = nums.length-1;
      int[] result = new int[] {-1,-1};
      if(nums.length == 0 || nums == null) return result;

      //serach for the left one
      while(left < right){
          int mid = (left + right)/2;
          if(nums[mid] < target) left = mid +1;
          else right = mid;
      }

      if(nums[left] != target) return result;
      else result[0] = left;

      //search for the right one
      right = nums.length-1;
      while(left < right){
          int mid = left + (right - left)/2 +1;
          if(nums[mid] > target) right = mid-1;
          else left = mid;
      }
      result[1] = right;
      return result;
  }
}