LeetCode 34. Find First and Last Position of Element in Sorted Array [Medium] [C++] 解題筆記

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].

EX:

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

        Output: [3,4]

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

        Output: [-1,-1]

想法:

        在 sorted 的 array 中找數字又要求複雜度 O(logn) 那一定就是用 binary search 拉，這題我們可以

直接使用 STL 中的 lower_bound 和 upper_bound 找到 第一個大於等於 target 的元素位置與 第一個大於 target 的元素的位置，

直接就可以得到 target 在數列中的範圍拉 !

完整程式碼:

解法一(binary search):

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> interval;
        int low = 0;
        int high = nums.size()-1;
        int mid = 0;
        while (low <= high) {
            mid = low + (high - low) / 2;
            if (nums.at(mid) > target) {
                high = mid - 1;
            }
            if (nums.at(mid) < target) {
                low = mid + 1;
            }
            if (nums.at(mid) == target) {
                if (nums.at(low) < target) {
                    low++;
                }
                if (nums.at(high) > target) {
                    high--;
                }
                if (nums.at(high) == target && nums.at(low) == target) {
                    break;
                }
            }
        
        }
        if (low > high) {
            interval.emplace_back(-1);
            interval.emplace_back(-1);
        }   
        else {
            interval.emplace_back(low);
            interval.emplace_back(high);
        }   
        return interval;
    }
};

解法二(binary search with STL):

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2, -1);
        auto low = lower_bound(nums.begin(), nums.end(), target);
        auto high = upper_bound(nums.begin(), nums.end(), target);
        if (low == nums.end() || *low != target) { return res; }
        if (high == nums.end()) {
            res[0] = low - nums.begin();
            res[1] = nums.size() - 1;
        }
        else {
            res[0] = low - nums.begin();
            res[1] = high - nums.begin() - 1;
        }
        return res;
    }
};