LeetCode 34 在排序數組中查找元素的第一個和最後一個位置

題目描述

給定一個按升序排列的整數數組 nums 和目標值 target，找出目標值在數組中的起始和結束位置。要求時間複雜度 O(log n)。若目標值不存在，返回 [-1, -1]。

範例：

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

解題思路：兩次二分查找

利用有序性，分別查找左邊界（第一個 ≥ target 的位置）和右邊界（第一個 > target 的位置 - 1）：

1. 查左邊界：mid 指向值 ≥ target 時向左縮，否則向右
2. 查右邊界：mid 指向值 > target 時向左縮，否則向右
3. 驗證左邊界是否真為 target，否則返回 [-1, -1]

時間複雜度：O(log n)，空間複雜度：O(1)。

Java 參考實現

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        int n = nums.length;
        if (n == 0) return result;
        
        // 查找左邊界：第一個 >= target 的位置
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        int start = left;
        
        // 目標不存在
        if (start == n || nums[start] != target) {
            return result;
        }
        
        // 查找右邊界：第一個 > target 的位置 - 1
        left = 0; right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        int end = right;
        
        result[0] = start;
        result[1] = end;
        return result;
    }
}

Python 參考實現

class Solution:
    def searchRange(self, nums, target):
        def lower_bound(arr, val):
            l, r = 0, len(arr)
            while l < r:
                mid = (l + r) // 2
                if arr[mid] >= val:
                    r = mid
                else:
                    l = mid + 1
            return l
        
        start = lower_bound(nums, target)
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        
        end = lower_bound(nums, target + 1) - 1
        return [start, end]

核心要點總結

• 左閉右開區間：[left, right) 統一邊界處理，避免死循環
• lower_bound 抽象：查找第一個 ≥ val 的位置，可復用於右邊界（查 target+1）
• 驗證存在性：二分查找只能定位位置，需額外檢查該位置值是否為 target
• 模板化思維：掌握「查左邊界/右邊界」兩個二分模板，覆蓋 90% 有序數組查找變體

這道題是二分查找邊界問題的標準範例，理解「第一個 ≥」與「第一個 >」的區別是關鍵。