LeetCode 34. 在排序陣列中查找元素的第一個和最後一個位置（二分查找圖解）

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 <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums 是一個非遞減陣列
• -10^9 <= target <= 10^9

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，題解連結。題解提到搭配影片「基礎算法精講 04」（原文沒有附連結，本文不放）。圖解與步驟說明為自行補充。

前置知識：二分查找與 lowerBound

二分查找是在「有序」的陣列裡，每次看中間的數，一次排除一半，所以只要 O(log n)。

這題的關鍵是把問題改寫成一個固定的小問題，叫 lowerBound：

lowerBound(nums, x)：回傳最小的滿足 nums[i] >= x 的下標 i。如果陣列為空，或所有數都 < x，回傳 nums.length。

紅藍染色的想法

因為陣列是非遞減的，把每個數和 x 比較：< x 的染成紅色，≥ x 的染成藍色，整個陣列一定長成「紅紅紅…藍藍藍…」。lowerBound 就是在找第一個藍色的下標。

二分查找的過程，就是不斷縮小「還沒確定顏色」的範圍：

• nums[mid] >= x：mid 是藍色，它右邊也全是藍色，範圍往左縮。
• nums[mid] < x：mid 是紅色，它左邊也全是紅色，範圍往右縮。

範圍縮到空的時候，紅和藍的交界就找到了。

思路：兩次 lowerBound

1. 開始位置 start = 第一個 ≥ target 的下標 = lowerBound(nums, target)。
   • 如果 start == nums.length，或 nums[start] != target，代表陣列裡根本沒有 target，回傳 [-1, -1]。
2. 結束位置 end = 最後一個 ≤ target 的下標。不用另外寫二分，可以複用 lowerBound：
   • 最後一個 ≤ target 的數，就是「第一個 > target 的數」左邊那一個。
   • 在全是整數的前提下，> target 等價於 ≥ target + 1，所以第一個 > target 的下標是 lowerBound(nums, target + 1)。
   • 減一就是 end：end = lowerBound(nums, target + 1) - 1。

用範例 1：target = 8。

• start = lowerBound(nums, 8) = 3（nums[3] = 8 是第一個 ≥ 8）。
• end = lowerBound(nums, 9) - 1 = 5 - 1 = 4（第一個 ≥ 9 是 nums[5] = 10，下標 5）。
• 答案 [3, 4]。

二分查找常用轉化表

這個表來自題解，換成不同需求都可以用 lowerBound 搞定（n 是陣列長度）：

需求	寫法	如果不存在
≥ x 的第一個元素的下標	lowerBound(nums, x)	結果為 n
> x 的第一個元素的下標	lowerBound(nums, x + 1)	結果為 n
< x 的最後一個元素的下標	lowerBound(nums, x) - 1	結果為 -1
≤ x 的最後一個元素的下標	lowerBound(nums, x + 1) - 1	結果為 -1

三種寫法，只差在「區間怎麼定義」

lowerBound 的內容就是二分查找，常見有三種寫法，差別只在「搜尋範圍」是哪一種區間：

	方法一：閉區間	方法二：左閉右開	方法三：開區間
區間	[left, right]	[left, right)	(left, right)
初始值	left = 0，right = n − 1	left = 0，right = n	left = −1，right = n
迴圈條件（區間不為空）	left <= right	left < right	left + 1 < right
nums[mid] >= x	right = mid − 1	right = mid	right = mid
nums[mid] < x	left = mid + 1	left = mid + 1	left = mid
迴圈結束後回傳	left（此時 left = right + 1）	left（此時 left = right）	right（此時 left + 1 = right）

怎麼判斷自己看到的是哪一種？看 while 的條件：left <= right 是閉區間，left < right 是左閉右開，left + 1 < right 是開區間。

下面三種寫法各自用同一個範例畫一遍：陣列 [5,7,7,8,8,10]，可以切換要找的是 lowerBound(nums, 8)（找 start）還是 lowerBound(nums, 9)（找 end）。兩端的 −∞、+∞ 是想像出來的哨兵（nums[−1] = −∞、nums[n] = +∞），這樣 −1 一定是紅色、n 一定是藍色。圖中 L、M、R 分別標出 left、mid、right。

方法一：閉區間

思路

搜尋範圍是閉區間 [left, right]，初始 left = 0、right = n − 1，left <= right 時範圍不為空。

迴圈不變量（每一輪開始時都成立）：

• nums[left − 1] < x（left 左邊全是紅色）
• nums[right + 1] >= x（right 右邊全是藍色）

每次取 mid：nums[mid] >= x 是藍色，mid 右邊都不用看，範圍縮到 [left, mid − 1]（right = mid − 1）；否則是紅色，範圍縮到 [mid + 1, right]（left = mid + 1）。

結束時 left = right + 1，此時 nums[left − 1] < x、nums[left] = nums[right + 1] >= x，所以 left 就是第一個 ≥ x 的下標。

圖解（可互動）

上一步 下一步 重置

nums = [5,7,7,8,8,10]，兩端的 −∞ 和 +∞ 是想像出來的哨兵（nums[−1] = −∞，nums[n] = +∞）

紅：已確定 < target 藍：已確定 ≥ target 白：還沒確定（搜尋範圍） mid

left0

right0

mid—

注意範圍縮到最後，left 和 right 會交錯（left = right + 1），白色格子消失，紅藍的交界就是答案。

解法（灵茶山艾府）

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1}; // nums 中沒有 target
        }
        // 如果 start 存在，那麼 end 必定存在
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    // lowerBound 回傳最小的滿足 nums[i] >= target 的下標 i
    // 如果陣列為空，或者所有數都 < target，則回傳 nums.length
    // 要求 nums 是非遞減的，即 nums[i] <= nums[i + 1]
    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; // 閉區間 [left, right]
        while (left <= right) { // 區間不為空
            // 迴圈不變量：
            // nums[left-1] < target
            // nums[right+1] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1; // 範圍縮小到 [left, mid-1]
            } else {
                left = mid + 1; // 範圍縮小到 [mid+1, right]
            }
        }
        // 迴圈結束後 left = right+1
        // 此時 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        // 所以 left 就是第一個 >= target 的元素下標
        return left;
    }
}

複雜度分析

• 時間複雜度：O(log n)，其中 n 是 nums 的長度。lowerBound 呼叫兩次，每次 O(log n)。
• 空間複雜度：O(1)。

方法二：左閉右開區間

思路

搜尋範圍是左閉右開 [left, right)，初始 left = 0、right = n，left < right 時範圍不為空。

迴圈不變量：nums[left − 1] < x、nums[right] >= x。

• nums[mid] >= x：mid 是藍色，它可能就是答案，所以右端點取到 mid（開區間不包含 mid，但 mid 已經是藍色，被記在右邊）：right = mid，範圍縮到 [left, mid)。
• nums[mid] < x：left = mid + 1，範圍縮到 [mid + 1, right)。

結束時 left = right，答案就是 left（等於 right）。

圖解（可互動）

和方法一比較：right 初始是 n（指向哨兵 +∞），更新時 right = mid 而不是 mid − 1，結束時 left 和 right 重合而不是交錯。

上一步 下一步 重置

nums = [5,7,7,8,8,10]，兩端的 −∞ 和 +∞ 是想像出來的哨兵（nums[−1] = −∞，nums[n] = +∞）

紅：已確定 < target 藍：已確定 ≥ target 白：還沒確定（搜尋範圍） mid

left0

right0

mid—

解法（灵茶山艾府）

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1}; // nums 中沒有 target
        }
        // 如果 start 存在，那麼 end 必定存在
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    // lowerBound 回傳最小的滿足 nums[i] >= target 的下標 i
    // 如果陣列為空，或者所有數都 < target，則回傳 nums.length
    // 要求 nums 是非遞減的，即 nums[i] <= nums[i + 1]
    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // 左閉右開區間 [left, right)
        while (left < right) { // 區間不為空
            // 迴圈不變量：
            // nums[left-1] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 範圍縮小到 [left, mid)
            } else {
                left = mid + 1; // 範圍縮小到 [mid+1, right)
            }
        }
        // 迴圈結束後 left = right
        // 此時 nums[left-1] < target 而 nums[left] = nums[right] >= target
        // 所以 left 就是第一個 >= target 的元素下標
        return left;
    }
}

複雜度分析

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

方法三：開區間

思路

搜尋範圍是開區間 (left, right)，初始 left = −1、right = n（這兩個下標都不在陣列裡，是兩個哨兵），left + 1 < right 時範圍不為空。

可以假設 nums[−1] = −∞、nums[n] = +∞，陣列仍然有序，所以 nums[−1] < x（紅）、nums[n] >= x（藍），這就是為什麼初始值是 −1 和 n。

迴圈不變量：nums[left] < x、nums[right] >= x，也就是 left 一直是紅色、right 一直是藍色。

• nums[mid] >= x：mid 是藍色，right = mid。
• nums[mid] < x：mid 是紅色，left = mid。

兩邊更新時都是「直接指向 mid」，不用加減一。結束時 left + 1 = right，left 是最後一個紅色、right 是第一個藍色，所以答案是 right。

圖解（可互動）

這個寫法最直接對應「紅藍染色」：L 永遠停在紅色格子、R 永遠停在藍色格子，兩者碰到一起（相鄰）就結束，答案是 R。

上一步 下一步 重置

nums = [5,7,7,8,8,10]，兩端的 −∞ 和 +∞ 是想像出來的哨兵（nums[−1] = −∞，nums[n] = +∞）

紅：已確定 < target 藍：已確定 ≥ target 白：還沒確定（搜尋範圍） mid

left0

right0

mid—

解法（灵茶山艾府）

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1}; // nums 中沒有 target
        }
        // 如果 start 存在，那麼 end 必定存在
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }

    // lowerBound 回傳最小的滿足 nums[i] >= target 的下標 i
    // 如果陣列為空，或者所有數都 < target，則回傳 nums.length
    // 要求 nums 是非遞減的，即 nums[i] <= nums[i + 1]
    private int lowerBound(int[] nums, int target) {
        int left = -1;
        int right = nums.length; // 開區間 (left, right)
        while (left + 1 < right) { // 區間不為空
            // 迴圈不變量：
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid; // 範圍縮小到 (left, mid)
            } else {
                left = mid; // 範圍縮小到 (mid, right)
            }
        }
        // 迴圈結束後 left+1 = right
        // 此時 nums[left] < target 而 nums[right] >= target
        // 所以 right 就是第一個 >= target 的元素下標
        return right;
    }
}

複雜度分析

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

答疑

以下整理自題解的問答，措辭為自行改寫。

Q：end = lowerBound(nums, target + 1) - 1 怎麼理解？
要找「最後一個 ≤ target」，等於找「第一個 > target」再往左一格。數字都是整數時 > target 就是 ≥ target + 1，所以直接複用 lowerBound。

Q：如果不存在 ≥ target + 1 的數怎麼辦？
代表所有數都 ≤ target。如果陣列裡有 target，那最後一個數（下標 n − 1）就是 target。lowerBound(nums, target + 1) 這時回傳 n，減一剛好是 n − 1，結果正確。

Q：為什麼寫 left + (right - left) / 2？
left + right 在陣列很長時可能 int 溢位，這種寫法不會。這題的資料範圍寫 (left + right) / 2 也不會出錯，但養成習慣比較安全。

Q：閉區間寫法裡，nums[mid] >= target 時為什麼 right = mid − 1，不會錯過答案嗎？
「二分範圍」和「答案所在範圍」是兩個概念。設目前二分範圍是 [L, R]，如果裡面所有數都 < target，答案是 R + 1，所以閉區間 [L, R] 的答案所在範圍是 [L, R + 1]。mid 如果是藍色，它右邊都是藍色，答案只會在 mid 或它左邊，而 right = mid − 1 之後，答案仍然在 [left, right + 1] 裡（right + 1 = mid 就是那個可能的答案），所以不會錯過。

Q：有些寫法會在二分過程中額外記錄答案，怎麼看？
喜歡這種寫法的人，建議用開區間。開區間裡 if 條件成立時更新哪個變數（right），最後就回傳哪個變數，效果和「記錄答案」一樣。

Q：開區間裡 −1 和 n 這兩個下標怎麼理解？
假設 nums[−1] = −∞、nums[n] = +∞，陣列仍然有序。這時 nums[−1] < target（紅），nums[n] >= target（藍），所以 −1 是紅色、n 是藍色。這個想法也能用在「二分答案」的題目。

Q：Java 的 Arrays.binarySearch 可以用嗎？
不行。陣列有多個 target 時，它回傳的不一定是第一個 ≥ target 的下標，所以拿不到 start。（Python 的 bisect_left 和 bisect_right 就是 lowerBound 的兩種版本，可以直接用。）