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

Medium

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

題目

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 <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums is a non-decreasing array.
• -10^9 <= target <= 10^9

解題思路

這題是很經典的找最小可行解和最大可行解的 Binary Search 題型

我的另一篇文章有解說 Binary Search 的解題思路，底家 XD：

Algorithm - Binary Search

因為 nums 已經排序好，所以可以分別用兩次 Binary Search：

• 第一次 Binary Search：

  • 找 target 第一次出現的位置
  • 也就是找最小可行解
  • 條件是：nums[mid] >= target
  • 如果 nums[mid] >= target
    • 代表答案可能在 mid
    • 也可能在更左邊
    • 所以 right = mid
  • 否則：
    • left = mid + 1

• 找最小可行解時：

  • 使用：
    • mid = left + (right - left) / 2
  • 因為這樣會偏左
  • 搭配 right = mid 可以避免無限迴圈

• 第二次 Binary Search：

  • 找 target 最後一次出現的位置
  • 也就是找最大可行解
  • 條件是：nums[mid] <= target
  • 如果 nums[mid] <= target
    • 代表答案可能在 mid
    • 也可能在更右邊
    • 所以 left = mid
  • 否則：
    • right = mid - 1

• 找最大可行解時：

  • 使用：
    • mid = left + (right - left + 1) / 2
  • 因為這樣會偏右
  • 搭配 left = mid 可以避免無限迴圈

• 最後要檢查：

  • 找到的 firstpos 是否真的等於 target
  • 找到的 lastpos 是否真的等於 target
  • 如果不是，代表 target 不存在，回傳 -1

Solution Code

Time Complexity
O(log n)

Space Complexity
O(1)

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        if(n == 0) return {-1, -1};

        int left = 0, right = n - 1;

        while(left < right){ // 找最小可行解
            int mid = left + (right - left) / 2;

            if(nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        int firstpos = left;
        if(nums[firstpos] != target) firstpos = -1;

        left = 0, right = n - 1;
        while(left < right){ // 找最大可行解
            int mid = left + (right - left + 1) / 2;

            if(nums[mid] <= target) left = mid;
            else right = mid - 1;
        }
        int lastpos = left;
        if(nums[lastpos] != target) lastpos = -1;

        return {firstpos, lastpos};
    }
};