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

Last updated on Dec 7, 2025

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

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

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

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

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

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

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        low, high = 0, len(nums) - 1
        left_boundary = -1 # 預設找不到
        right_boundary = -1

        while low <= high:
            mid = low + (high - low) // 2
            
            # 關鍵判斷：當 nums[mid] >= target 時，mid 可能是答案，或答案在更左邊
            if nums[mid] >= target:
                left_boundary = mid   # 暫存這個潛在答案
                high = mid - 1        # 繼續向左邊區間探索
            else: # nums[mid] < target
                low = mid + 1         # 答案一定在右邊區間

        left_boundary = -1 if left_boundary != -1 and target != nums[left_boundary] else left_boundary

        low, high = 0, len(nums) - 1
        while low <= high:
            mid = low + (high - low) // 2
            
            # 關鍵判斷：當 nums[mid] >= target 時，mid 可能是答案，或答案在更左邊
            if nums[mid] <= target:
                right_boundary = mid   # 暫存這個潛在答案
                low = mid + 1          # 繼續向右邊區間探索
            else: # nums[mid] > target
                high = mid - 1         # 答案一定在左邊區間
        
        right_boundary = -1 if right_boundary != -1 and target != nums[right_boundary] else right_boundary

        return [left_boundary, right_boundary]