阿里算法面试真题：搜索区间

描述
给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。
如果目标值不在数组中，则返回[-1, -1]

在线评测地址：领扣题库官网

样例1
输入:
[]
9
输出:
[-1,-1]

样例2
输入:
[5, 7, 7, 8, 8, 10]
8
输出:
[3, 4]

算法：二分
算法思路

• 由于给定的是一个有序数组，具有单调性，因此很容易想到二分。
• 二分查找target的第一次出现的位置和最后一次出现的位置，最后输出即可。
• 具体实现：
• 对于一个长度为n的升序数组A，二分查找的区间为[0, n - 1]，定义left = 0, right = n - 1，中间值mid = left + (right - left) / 2 。
  1. 当 A[mid] > target 时，显然这时查找数值偏大，说明答案在左区间，因此使 right = mid 来缩小查找数值。
  2. 当 A[mid] < target 时，显然这时查找数值偏小，说明答案在右区间，因此使 left = mid 来放大查找数值。
  3. 当 A[mid] == target 时，为了寻找target出现的最左端(第一次出现位置)时，我们选择左区间作为下一次二分区间，因此使 right = mid；为了寻找target出现的最右端(最后一次出现位置)时，我们选择右区间作为下一次二分区间，因此使 left = mid 。
     综上所述：
• 当我们寻找target的左端点即第一次出现的位置时：
  1. 当 A[mid] < target 时， left = mid ；否则 right = mid。
  2. 最后优先判断并选取接近左边的 left 再判断 right
• 当我们寻找target的右端点即最后一次出现的位置时：
  1. 当 A[mid] <= target 时， left = mid ；否则 right = mid。
  2. 最后优先判断并选取接近右边的 right 再判断 left
     复杂度分析
• 常数级别的额外空间，空间复杂度O(1)。

• 两个二分，时间复杂度O(logn)。

  public class Solution {
  /**
   * @param A: an integer sorted array
   * @param target: an integer to be inserted
   * @return: a list of length 2, [index1, index2]
   */
  // 寻找左端点
  static int findFirstTargetNum(int[] A, int target, int n){
      int left = 0, right = n - 1;
      while (left + 1 < right){
          int mid = left + (right - left) / 2;
          if (A[mid] < target){
              left = mid;
          }
          else{
              right = mid;
          }
      }
      if (left < n && A[left] == target){
          return left;
      }
      if (right >= 0 && A[right] == target){
          return right;
      }
      return -1;
  }
  
  // 寻找右端点
  static int findLastTargetNum(int[] A, int target, int n){
      int left = 0, right = n - 1;
      while (left + 1 < right){
          int mid = left + (right - left) / 2;
          if (A[mid] <= target){
              left = mid;
          }
          else{
              right = mid;
          }
      }
      if (right >= 0 && A[right] == target){
          return right;
      }
      if (left < n && A[left] == target){
          return left;
      }
      return -1;
  }
  
  public int[] searchRange(int[] A, int target) {
      int n = A.length;
      int[] interval = {-1, -1};
      interval[0] = findFirstTargetNum(A, target, n);
      interval[1] = findLastTargetNum(A, target, n);
      return interval;
  }
  }

  更多题解参考：九章官网solution