34.在排序數(shù)組中尋找元素的第一個(gè)和最后一個(gè)位置

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。請你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(log n) 的算法解決此問題。

鏈接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array

示例 1:

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例 2:

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]     

示例 3:

輸入：nums = [], target = 0
輸出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一個(gè)非遞減數(shù)組
• nums 是一個(gè)非遞減數(shù)組

思路分析：

這也是一道典型的二分查找的問題，與之前不同的是，需要找出元素第一次出現(xiàn)的位置和最后一次出現(xiàn)的位置，而若是元素沒有出現(xiàn)過的話，需要返回?cái)?shù)組[-1,-1]，這里可以在最后利用一個(gè)判斷語句進(jìn)行判斷，如下：

 if (a <= b && b < (int)nums.size() && nums[a] == target && nums[b] == target)
        {
            return vector<int>{a, b};
        }
        return {-1,-1};

那么總的套路還是一樣的，仍然可以參考我之前總結(jié)的二分查找的多個(gè)不同模板進(jìn)行求解。

(3條消息) 【LeetCode704.二分查找】——二分查找方法匯總_一粒蛋TT的博客-CSDN博客

左分右邊法：

class Solution {
public:
    //求出第一次出現(xiàn)位置
    int target(vector<int>& nums, int target) {
        int l = -1;
        int r = (int)nums.size();
        while ((l + 1) != r)
        {
            int m = (l + r) / 2;
            //cout << "m=" << m<<endl;
            if (nums[m] < target)
            {
                l = m;
            }
            else
            {
                r = m;
            }
        }
        cout << "target1=" << r << endl;
        return r;
    }
    //求出最后一次出現(xiàn)的位置
    int targettwo(vector<int>& nums, int target)
    {
        int l = -1;
        int r = (int)nums.size();
        while ((l + 1) != r)
        {
            int m = (l + r) / 2;
            //cout << "m=" << m<<endl;
            if (nums[m] <= target)
            {
                l = m;
            }
            else
            {
                r = m;
            }
        }
        cout << "target2=" << l << endl;
        return l;
    }

    vector<int> searchRange(vector<int>& nums, int target )
    {
        int a = this->target(nums, target );
        int b = this->targettwo(nums, target );
        if (a <= b && b < (int)nums.size() && nums[a] == target && nums[b] == target)
        {
            return vector<int>{a, b};
        }
        return {-1,-1};
    }
};

左閉右閉法：

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

    vector<int> searchRange(vector<int>& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
            return vector<int>{leftIdx, rightIdx};
        } 
        return vector<int>{-1, -1};
    }
};

利用STL庫：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) {
            return {-1, -1};
        }
        int leftIdx = lower_bound(nums.begin(), nums.end(), target)-nums.begin();
        int rightIdx = upper_bound(nums.begin(), nums.end(), target)-1-nums.begin();
        if(leftIdx<=rightIdx && rightIdx<nums.size() && nums[leftIdx]==target && nums[rightIdx]==target) {
            return {leftIdx, rightIdx};
        }
        return {-1, -1};
    }
};

利用CPP中的STL庫函數(shù)，我們可以更快的直接求出元素的第一次出現(xiàn)位置以及最后一次出現(xiàn)的位置。這部分代碼參考了leetcode隨心源的題解。

總的來說，該題是對之前簡單二分查找的一個(gè)延伸拓展。

后續(xù)也會(huì)堅(jiān)持更新我的LeetCode刷題筆記，歡迎大家關(guān)注我，一起學(xué)習(xí)。
如果這篇文章對你有幫助，或者你喜歡這篇題解，可以給我點(diǎn)個(gè)贊哦。
CSDN同步更新，歡迎關(guān)注我的博客：一粒蛋TT的博客_CSDN博客-LeetCode學(xué)習(xí)筆記,HTML+CSS+JS,數(shù)據(jù)結(jié)構(gòu)領(lǐng)域博主

往期回顧：
LeetCode367.有效的完全平方數(shù)
LeetCode69.x的平方根
LeetCode35.搜索插入位置
LeetCode704.二分查找