P109 有序数组中查找数字的开始和结束下标

描述#

这个题目说的是，给你一个递增排序的数组和一个目标值，你要找到目标值在这个数组中的开始下标和结束下标。如果找不到目标值，就返回 [-1, -1]。

比如说，给你的递增数组是：
1, 2, 2, 4, 4, 8, 8
给你的目标值是 2。2 在这个数组中的开始下标是 1，结束下标是 2，于是你要返回：
[1, 2]
如果给你的目标值是 0，0 不在这个数组中，因此你要返回：
[-1, -1]

相关视频：36. 二分搜索

代码#

public class AlgoCasts {

  // Time: O(n), Space: O(1)
  public int[] findFirstAndLastPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0) return new int[]{-1, -1};
    int n = nums.length, start = -1, end = -1;
    for (int i = 0; i < n; ++i) {
      if (nums[i] == target) {
        start = i;
        break;
      }
    }
    for (int j = n-1; j >= 0; --j) {
      if (nums[j] == target) {
        end = j;
        break;
      }
    }
    return new int[]{start, end};
  }

  private int binarySearchLastOne(int[] nums, int target) {
    int low = 0, high = nums.length - 1;
    while (low <= high) {
      int mid = low + (high - low) / 2;
      if (target < nums[mid]) high = mid - 1;
      else low = mid + 1;
    }
    return high;
  }

  // Time: O(log(n)), Space: O(1)
  public int[] binarySearchFirstAndLastPosition(int[] nums, int target) {
    if (nums == null || nums.length == 0) return new int[]{-1, -1};
    int end = binarySearchLastOne(nums, target);
    int start = binarySearchLastOne(nums, target-1) + 1;
    if (start >= 0 && start <= end && end < nums.length)
      return new int[]{start, end};
    else return new int[]{-1, -1};
  }

}