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

[frdmu]

Given an array of integers nums sorted in ascending 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

两次使用二分法，第一次找第一个=target的元素，第二次找第一个>target的元素。代码如下：

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

        return res;
    }
};

类似题目：
[剑指 Offer] 53 - I. 在排序数组中查找数字 I