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

Last updated on Apr 3, 2024

這一題是一個非常好的二分搜索的尋找左邊界與右邊界的問題。

題目給定的是一個排序好的陣列，陣列內的元素會有重複，以及一個數值，目標就是要看這個陣列是否存在這個值，並且因為元素會有重複，題目所要求的是回傳這個數值最左邊的位置以及最右邊的位置。

這個題目存在著夠快的線性時間 \(O(n)\) 的解法，當然這並不是最佳的解法，通常可以想到可以用二分搜索的方式來搜尋，不過需要注意的是陣列存在著重複的元素，要怎麼處理？

首先先處理左邊界的情況：

當找到某個位置，其值剛好等於目標時，再檢查三件事情
1. 該位置是不是剛好是最左邊界的位置？如果是的話代表最目前的左邊界就是目標數值的最左邊界。
2. 該位置不是在最左邊界：
  1. 前一個位置的值比自己小，這樣也代表現在這個位置是最左邊界。（因為還沒有碰到最左邊界，所以不用擔心指針的位置超過陣列的範圍）
  2. 前一個位置的值剛好等於自己，代表左邊還有數值跟目標依樣，此時右邊界往左縮一格。
如果該位置的數值比目標大，代表要往左側搜尋，移動右邊界到目前位置的前一個位置。
如果該位置的數值比目標小，代表要往右側搜尋，移動左邊界到目前位置的下一個位置。
繼續搜尋

以上反之即為尋找右邊界的邏輯。

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        leftBound = -1
        rightBound = -1
        left = 0
        right = len(nums) - 1
        
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                if mid == left or nums[mid - 1] < target:
                    leftBound = mid
                    break
                else:
                    right -= 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        
        left = 0
        right = len(nums) - 1
        while left <= right: 
            mid = left + (right - left) // 2
            if nums[mid] == target:
                if mid == right or nums[mid + 1] > target:
                    rightBound = mid
                    break
                else:
                    left += 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                left = mid + 1
        
        return [leftBound, rightBound]