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

(https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/)

二分法

此題不像之前的二分查找題目，若只用一個二分查找很混亂，因此我推薦用兩個二分法更為得當，分別去找滿足條件的左右邊界
尋找target的左右邊界，存在三種情況：
- target不滿足陣列內大小范圍
- target滿足陣列大小范圍，但陣列內不存在target
- target既滿足陣列大小范圍，且陣列記憶體在target

接下來即可運用兩個二分法（左閉右閉）去找滿足條件的左右邊界：

左邊界：若陣列中存在target的話，那么最后一輪回圈，left和right都必將指向target值，又因為 if( nums[middle] >= target ) right = middle - 1，right肯定會指向最左邊的target，最后，right會繼續向左移動，因此left是左邊界的答案
```
while(left <= right)
{
    int middle = left + ( ( right - left ) >> 1 );

    if( nums[middle] >= target ) right = middle - 1;
    else left = middle + 1;
}

int L = left;
```

右邊界：與左邊界同理

while(left <= right)
{
    int middle = left + ( ( right - left ) >> 1 );

    if( nums[middle] <= target ) left = middle + 1;
    else right = middle - 1;
}

int R = right;

全部實作：

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

        int left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int middle = left + ( ( right - left ) >> 1 );

            if( nums[middle] >= target ) right = middle - 1;
            else left = middle + 1;
        }

        //左邊界
        int L = left;
        
        left = 0, right = nums.size() - 1;

        while(left <= right)
        {
            int middle = left + ( ( right - left ) >> 1 );

            if( nums[middle] <= target ) left = middle + 1;
            else right = middle - 1;
        }

        //右邊界
        int R = right;

        //處理三種情況
        if( L > R ) return {-1, -1};

        return {L, R};
    }
};

時間復雜度：O(log_n)

空間復雜度：O(1)

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/514193.html

標籤：其他

上一篇：行為樹的優缺點

下一篇：資料結構（嚴蔚敏版）第三章——堆疊和佇列（二）【堆疊的表示和操作的實作】

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

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

二分法