Leetcode 34. 在排序陣列中查找元素的第一個和最后一個位置 【陣列 二分查找】

Leetcode 34. 在排序陣列中查找元素的第一個和最后一個位置

給定一個按照升序排列的整數陣列 nums，和一個目標值 target，找出給定目標值在陣列中的開始位置和結束位置，

如果陣列中不存在目標值 target，回傳 [-1, -1]，

進階：

你可以設計并實作時間復雜度為 O(log n) 的演算法解決此問題嗎？

示例 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 是一個非遞減陣列

• 109 <= target <= 109

思路分析

最基本的二分查找法 704. 二分查找，是在升序排列的陣列中查找元素，找到了就回傳，找不到就回傳-1，所謂的找到就是target == nums[mid]，

本題目是要查找元素出現的第一個和最后一個位置，

1. 查找元素出現的第一個位置：
   • 當target == nums[mid] 時，不能立即回傳，要縮小右半區間，看左半區間是否還存在要查找的元素，
   • 當target > nums[mid] 時， 說明target還在mid右側，第一個target也在mid右側，所以縮小左邊界，
   • 當target < nums[mid] 時， 說明target還在mid左側，應該縮小右邊界，
2. 查找元素出現的最后一個位置：
   • 當target < nums[mid]， 縮小右邊界，
   • 當target == nums[mid]，不能立即回傳，縮小左邊界，在右半部分繼續查找元素，
   • 當target > nums[mid]，縮小左邊界，

規定：使用左閉右閉區間[left, right]

一、查找元素在排序陣列的第一個位置

問題一：在查找元素在排序陣列中的第一個位置時，如果元素存在，那么最后回傳的是left還是right？

**回傳left，**由于是在閉區間[left, right]中查找第一個位置，當target == nums[mid] 的時候，這時找到的可能就是第一個元素，但是，為了確認左半區間還沒有該元素，就會把right的值設為mid - 1，那么當左半部分查找不到該元素的時候，left最終的值就會是之前mid的值，

問題二：在查找元素在排序陣列中的第一個位置時，怎么確定元素不存在呢？

當要查找的元素大于排序陣列中所有元素時（即元素在陣列右邊界外）

比如，要在排序陣列{5, 7, 7, 8, 8, 10}中查找目標元素target=15，這時target=15大于陣列中所有的元素，那么查找結束時right=nums.length-1，left=nums.length，即left超出了陣列nums的最大索引nums.lenght-1，由于上面已經確定最侄訓傳left，因此在這種情況下元素不存在的條件是left==nums.length，

當要查找的元素小于排序陣列中所有元素時（即元素在左邊界外）

比如，要在排序陣列{5, 7, 7, 8, 8, 10}中查找目標元素target=2，這時target = 2小于陣列中所有的元素，那么在查找結束時right = -1， left = 0，這時元素不存在的條件 nums[left]!=target，

當要查找的元素大于排序陣列中最小元素，小于排序陣列中最大元素時（即元素在區間范圍內）

比如，要在排序陣列{5, 7, 7, 8, 8, 10}中查找目標元素target=9，這時target=9雖然在排序陣列中不存在，但其大于陣列中最小元素，小于陣列中最大元素，因此，查找結束時left=5和right=4，也就是說在這種情況下，當目標元素在陣列中不存在時，left的值是在區間[0，nums.lenght-1]內的，同樣的，這時元素不存在的條件是nums[left]!=target，

**綜上所述：**在左閉右閉區間[left, right]內查找元素的第一個位置時，如果目標元素存在，回傳left；元素不存在的判斷條件是 一是left==nums.length，二是nums[left]!=target，

Demo

int getleftposition(vector<int>& nums, int target) {
    //規定：左閉右閉區間 
    int left = 0, right = nums.size() - 1; 
    while(left <= right) {
        int mid = left + ((right - left) >> 1);
          if(target > nums[mid]) {
              //target在mid值右側，縮小左半區間
              left = mid + 1;
           } else if (target < nums[mid]) {
              right = mid - 1;
           } else {
              // target == nums[mid]
              // 縮小右半區間，在左半區間繼續尋找是否存在target
              right = mid - 1;
           }
     }

     if(left == nums.size() || nums[left] != target)
         return -1;
        
     return left;
}   

二、查找元素在排序陣列中的最后一個位置

問題一：在查找元素在排序陣列中的最后一個位置時，如果元素存在，那么最后是回傳left還是right呢？

**回傳right，**由于是在閉區間[left,right]中查找最后一個位置，那么當target==nums[mid]時，這時找到的可能就是最后一個元素，但是，為了確認右半部分還有沒有該元素，會將left的值設定為mid+1，此時由于陣列是升序排列的，那么當右半部分查找不到該元素時，right最終的值就會是之前mid的值，

問題二：在查找元素在排序陣列中的最后一個位置時，怎么確定元素不存在呢？

當要查找的元素大于排序陣列中所有元素時（即元素在陣列右邊界外）

比如，要在排序陣列{5, 7, 7, 8, 8, 10}中查找目標元素target=15，這時target=15大于陣列中所有的元素，那么查找結束時right=nums.length-1，left=nums.length，由于上面已經確定最侄訓傳right，因此在這種情況下元素不存在的條件是nums[right]!=target，

當要查找的元素小于排序陣列中所有元素時（即元素在左邊界外）

比如，要在排序陣列{5, 7, 7, 8, 8, 10}中查找目標元素target=-2，這時target=-2小于陣列中所有的元素，那么查找結束時right=-1，left=0，同樣的，由于上面已經確定最侄訓傳right，因此在這種情況下元素不存在的條件是right==-1，

當要查找的元素大于排序陣列中最小元素，小于排序陣列中最大元素時

比如，要在排序陣列{5, 7, 7, 8, 8, 10}中查找目標元素target=9，這時target=9雖然在排序陣列中不存在，但其大于陣列中最小元素，小于陣列中最大元素，因此，查找結束時left=5和right=4，也就是說在這種情況下，當目標元素在陣列中不存在時，right的值是在區間[0，nums.lenght-1]內的，此時，元素不存在的條件是nums[right]!=target，

根據上述分析，我們確定了在左閉右閉的區間[left,right]內查找元素的最后一個位置時，如果目標元素存在，則回傳right；元素不存在的判斷條件一是right==-1，二是nums[right]!=target，

Demo

int getrightposition(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = left + ((right - left) >> 1);
        if(target < nums[mid]) {
            right = mid - 1;
        } else if (target == nums[mid]) {
            // 往右邊區間繼續找是不是最后一個target
            left = mid + 1;
         } else {
            // target > nums[mid]
            left = mid + 1;
        }
    }

    if(right == - 1 || nums[right] != target) {
        return -1;
    }

    return right;
} 

C++ 題解

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans(2, -1);
        ans[0] = getleftposition(nums, target);
        ans[1] = getrightposition(nums, target);
        return ans;
    }

private:
    int getleftposition(vector<int>& nums, int target) {
        //規定：左閉右閉區間 
        int left = 0, right = nums.size() - 1; 
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(target > nums[mid]) {
                //target在mid值右側，縮小左半區間
                left = mid + 1;
            } else if (target < nums[mid]) {
                right = mid - 1;
            } else {
                // target == nums[mid]
                // 縮小右半區間，在左半區間繼續尋找是否存在target
                right = mid - 1;
            }
        }

        if(left == nums.size() || nums[left] != target)
            return -1;
        
        return left;
    }   

    int getrightposition(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(target < nums[mid]) {
                right = mid - 1;
            } else if (target == nums[mid]) {
                // 往右邊區間繼續找是不是最后一個target
                left = mid + 1;
            } else {
                // target > nums[mid]
                left = mid + 1;
            }
        }

        if(right == - 1 || nums[right] != target) {
            return -1;
        }

        return right;
    } 
};

時間復雜度：O (log n)

空間復雜度: O (1)