Question

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]

Difficulty:Medium

Category:Array, Binary-Search

Analyze

Solution

在第一个 Binary Search 里面, 寻找 lower bound 的时候,有两种情况:

  • 如果目标数字比数组中所有数值都要大,那么 Left 指针会一直移动到超出数组索引
  • 如果目标数字比数组中所有数字都要小的话, 那么,right指针会一直移动到0的位置

所以在这个位置的去数值要比较特殊:如果使用的是:int left = 0, right = nums.size();, 那么在使用left or right进行索引的时候, 一定要判断是否超出索引。

class Solution {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res(2, -1);
    int left = 0, right = nums.size() - 1;
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] < target)
        left = mid + 1;
      else
        right = mid;
    }
    if (nums[right] != target) return res;
    res[0] = right;

    // Do the second Binary Search
    right = nums.size();
    while (left < right) {
      int mid = left + (right - left) / 2;
      if (nums[mid] <= target)
        left = mid + 1;
      else
        right = mid;
    }
    res[1] = left - 1;
    return res;
  }
};

Solution 2: DFS

class Solution {
 public:
  vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res = {-1, -1};
    int index_x = search(nums, target);
    if (index_x == -1) return res;
    int index_left = index_x, index_right = index_x;
    while (index_left && nums[index_left - 1] == target) index_left--;
    while (index_right < nums.size() - 1 && nums[index_right + 1] == target) index_right++;
    res[0] = index_left;
    res[1] = index_right;
    return res;
  }

  int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left != right) {
      const int mid = left + (right - left) / 2;
      if (nums[mid] == target) return mid;
      if (nums[left] < nums[mid]) {
        if (nums[left] <= target && nums[mid] > target) {
          right = mid;
        } else {
          left = mid + 1;
        }
      } else if (nums[left] == nums[mid]) {
        left++;
      } else {
        if (nums[mid] < target && nums[right - 1] >= target) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
    }
    return -1;
  }
};
By guozetang            Updated: 2020-09-19 13:02:30

results matching ""

    No results matching ""