Question

34. Find First and Last Position of Element in Sorted Array

中文文档

Description

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

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

You must write an algorithm with O(log n) runtime complexity.

 

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]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

 

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

Solutions

Solution 1: Binary Search

We can perform binary search twice to find the left and right boundaries respectively.

The time complexity is $O(\log n)$, and the space complexity is $O(1)$. Here, $n$ is the length of the array $nums$.

Below are two general templates for binary search:

Template 1:

boolean check(int x) {
}

int search(int left, int right) {
  while (left < right) {
    int mid = (left + right) >> 1;
    if (check(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  return left;
}

Template 2:

boolean check(int x) {
}

int search(int left, int right) {
  while (left < right) {
    int mid = (left + right + 1) >> 1;
    if (check(mid)) {
      left = mid;
    } else {
      right = mid - 1;
    }
  }
  return left;
}

When doing binary search problems, you can follow the following routine:

1. Write out the loop condition $left < right$;
2. Inside the loop, you might as well write $mid = \lfloor \frac{left + right}{2} \rfloor$ first;
3. According to the specific problem, implement the $check()$ function (sometimes the logic is very simple, you can not define $check$), think about whether to use $right = mid$ (Template $1$) or $left = mid$ (Template $2$);
   • If $right = mid$, then write the else statement $left = mid + 1$, and there is no need to change the calculation of $mid$, that is, keep $mid = \lfloor \frac{left + right}{2} \rfloor$;
   • If $left = mid$, then write the else statement $right = mid - 1$, and add +1 when calculating $mid$, that is, $mid = \lfloor \frac{left + right + 1}{2} \rfloor$;
4. When the loop ends, $left$ equals $right$.

Note that the advantage of these two templates is that they always keep the answer within the binary search interval, and the value corresponding to the end condition of the binary search is exactly at the position of the answer. For the case that may have no solution, just check whether the $left$ or $right$ after the binary search ends satisfies the problem.

class Solution:
  def searchRange(self, nums: List[int], target: int) -> List[int]:
    l = bisect_left(nums, target)
    r = bisect_left(nums, target + 1)
    return [-1, -1] if l == r else [l, r - 1]

class Solution {
  public int[] searchRange(int[] nums, int target) {
    int l = search(nums, target);
    int r = search(nums, target + 1);
    return l == r ? new int[] {-1, -1} : new int[] {l, r - 1};
  }

  private int search(int[] nums, int x) {
    int left = 0, right = nums.length;
    while (left < right) {
      int mid = (left + right) >>> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  vector<int> searchRange(vector<int>& nums, int target) {
    int l = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    int r = lower_bound(nums.begin(), nums.end(), target + 1) - nums.begin();
    if (l == r) return {-1, -1};
    return {l, r - 1};
  }
};

func searchRange(nums []int, target int) []int {
  l := sort.SearchInts(nums, target)
  r := sort.SearchInts(nums, target+1)
  if l == r {
    return []int{-1, -1}
  }
  return []int{l, r - 1}
}

function searchRange(nums: number[], target: number): number[] {
  const search = (x: number): number => {
    let [left, right] = [0, nums.length];
    while (left < right) {
      const mid = (left + right) >> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  };
  const l = search(target);
  const r = search(target + 1);
  return l === r ? [-1, -1] : [l, r - 1];
}

impl Solution {
  pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
    let n = nums.len();
    let search = |x| {
      let mut left = 0;
      let mut right = n;
      while left < right {
        let mid = left + (right - left) / 2;
        if nums[mid] < x {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      left
    };
    let l = search(target);
    let r = search(target + 1);
    if l == r {
      return vec![-1, -1];
    }
    vec![l as i32, (r - 1) as i32]
  }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
  function search(x) {
    let left = 0,
      right = nums.length;
    while (left < right) {
      const mid = (left + right) >> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
  const l = search(target);
  const r = search(target + 1);
  return l == r ? [-1, -1] : [l, r - 1];
};