題目與適用情境
給定一個按非遞減順序排列的整數陣列 nums 和整數 target，回傳 target 在陣列中的第一個和最後一個 索引；若目標值不存在，回傳 [-1, -1]。陣列可以為空，可以包含重複值，函式不得修改輸入。要求時間複雜度 為 O(log n)，額外空間為 O(1)。
例如，nums = [1, 2, 2, 2, 3] 且 target = 2 時回傳 [1, 3]；target = 4 時回傳 [-1, -1]。線性掃描當然能得到答案，但最差時間是 O(n)，不符合題目要求。
這道題適合軟體工程師和演算法職缺的程式設計輪。Amazon 目前的 SDE II 面試指引要求寫出語法正確、可擴展、 穩健且經過邊界驗證的程式碼；LeetCode 也保留了相同核心問題。真正的考點不是背下兩個模板，而是能否先寫出 搜尋邊界的精確定義，再讓迴圈條件、區間更新和回傳值都遵守同一個不變量。
面試官考察重點
首先看候選人是否辨識到「找到任意一個目標值」還不夠。普通二分搜尋在遇到相等值時立即回傳，無法保證它是 最左或最右位置；找到後再向兩邊線性擴展，在陣列全部等於目標值時仍會退化為 O(n)。
第二個考點是邊界語意。建議把問題拆成兩個插入點：
lowerBound：第一個大於等於target的位置。upperBound：第一個嚴格大於target的位置。
Python 官方 bisectleft 和 bisectright 使用相同分割定義。只要這兩個位置正確，目標存在時答案就是 [lowerBound, upperBound - 1]。
第三個考點是迴圈不變量。使用半開區間 [left, right) 時，空陣列自然表示為 [0, 0)；迴圈結束條件是 left === right。如果程式混用閉區間和半開區間，例如把 right 初始化為 nums.length，卻又存取 nums[right]，就會產生越界或無限迴圈。
最後看驗證能力。強回答會涵蓋空陣列、單一元素、全部重複、目標小於最小值、目標大於最大值、目標位於兩端和 目標不存在，還會說明為什麼 target + 1 不是通用的 upper bound 寫法：它依賴離散數值的「後繼」， 會在最大安全整數處建立約束域外的值，也無法直接推廣到字串或自訂比較器。
回答前需要釐清的問題
- 陣列是否已經排序？ 本題保證非遞減。如果未排序，必須先排序並保留原索引，整體就不再是
O(log n)。 - 回傳原陣列索引還是排序後索引？ 本題輸入已排序，兩者相同；若允許先排序，這會改變資料結構。
- 目標不存在時回傳什麼？ 本題固定回傳
[-1, -1]，不能把插入點誤當成命中位置。 - 允許重複值嗎？ 允許，而且重複值正是需要邊界二分的原因。
- 陣列可以為空嗎？ 可以。半開區間實作不需單獨存取首尾元素，能自然回傳未命中。
- 數值範圍是什麼？ 使用 JavaScript 安全整數。實作不計算
target + 1，因此不會為了搜尋邊界建立約束域外的哨兵值。 - 是否必須手寫二分搜尋？ 面試題要求手寫；生產程式若標準函式庫契約完全相符，應優先重用標準函式庫。
- 能否修改陣列？ 不能，也不需要。兩個搜尋都只讀取陣列。
30 秒回答框架
「我會做兩次邊界二分，不會找到一個目標後線性擴展。lowerBound 在半開區間 [left, right) 中找第一個 大於等於 target 的位置；upperBound 找第一個嚴格大於 target 的位置。迴圈中使用 middle = left + floor((right - left) / 2)。若中點仍在目標左側，就令 left = middle + 1， 否則收縮 right = middle。先檢查 lower bound 是否越界或不等於目標；存在時回傳 [lower, upper - 1]。兩次搜尋都是 O(log n)，額外空間 O(1)。」
分步深入解答
第一步：把「首尾位置」改寫為兩個分割點。
對 nums = [1, 2, 2, 2, 3] 和 target = 2：
lowerBound = 1 // 第一個 nums[i] >= 2
upperBound = 4 // 第一個 nums[i] > 2
answer = [1, 4 - 1] = [1, 3]這種定義比「繼續往左找」和「繼續往右找」更容易驗證。目標不存在時，兩個插入點仍有意義。例如 target = 4 時兩者都等於陣列長度 5，但這不代表目標存在，因此必須另外檢查 nums[lower] === target。
第二步：固定半開區間不變量。
lowerBound 在每輪開始時維持：
- 所有索引小於
left的值都嚴格小於target。 - 所有索引大於等於
right的值都大於等於target。 - 尚未確定的候選區間是
[left, right)。
初始時 left = 0、right = nums.length，區間外沒有元素，不變量成立。若 nums[middle] < target， 中點及其左側都不可能是答案，因此令 left = middle + 1。否則中點可能就是第一個合格位置，不能丟掉， 所以令 right = middle。
每輪都嚴格縮短區間。當 left === right 時沒有未確定元素；左側全部小於目標，右側全部大於等於目標， 因此這個位置就是第一個大於等於目標的位置。
upperBound 使用相同框架，只把分割條件改成：
- 所有索引小於
left的值都小於等於target。 - 所有索引大於等於
right的值都嚴格大於target。
因此當 nums[middle] <= target 時移動 left，否則收縮 right。
第三步：實作兩個邊界函式。
function lowerBound(nums: number[], target: number): number {
let left = 0;
let right = nums.length;
while (left < right) {
const middle = left + Math.floor((right - left) / 2);
if (nums[middle] < target) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
}
function upperBound(nums: number[], target: number): number {
let left = 0;
let right = nums.length;
while (left < right) {
const middle = left + Math.floor((right - left) / 2);
if (nums[middle] <= target) {
left = middle + 1;
} else {
right = middle;
}
}
return left;
}兩段程式碼只有比較條件不同。保留兩個有明確名稱的函式，比傳入一個難讀的布林開關更適合面試說明，也避免 為了單一呼叫提前抽象複雜的通用框架。
中點寫成 left + floor((right - left) / 2)，不會先把兩個大索引相加。JavaScript 陣列長度受執行環境 限制，本題通常不會觸發數值溢位，但這種寫法可以直接移植到固定寬度整數語言。
第四步：組合結果並驗證目標真的存在。
function searchRange(nums: number[], target: number): [number, number] {
const first = lowerBound(nums, target);
if (first === nums.length || nums[first] !== target) {
return [-1, -1];
}
return [first, upperBound(nums, target) - 1];
}檢查順序很重要。先判斷 first === nums.length，再讀取 nums[first]，避免把陣列尾端之外的位置當成元素。 一旦確認 first 命中，upperBound 必定至少為 first + 1，所以減一後得到最後一個目標值索引。
不要用 lowerBound(nums, target + 1) - 1 代替 upper bound。在本題的安全整數約束下，它可能得到正確 結果，但當 target 是 Number.MAXSAFEINTEGER 時，加一已經超出保證精確整數運算的約束域；若輸入 擴展到任意 JavaScript Number，相鄰整數還可能因精度合併。字串、BigInt 或自訂比較器也沒有統一的 「下一個值」。直接搜尋第一個嚴格大於目標的位置才是完整語意。
第五步：證明複雜度。
每次迴圈把候選區間從長度 k 縮到至多約 k / 2，所以每個邊界函式執行 O(log n) 次比較。兩次搜尋 的總時間仍是 O(log n)。演算法只保存常數個索引，額外空間是 O(1)，也不會修改輸入陣列。
若先找到任意目標再向兩邊掃描，[2, 2, ..., 2] 會掃描全部 n 個元素，最差時間變為 O(n)。 若使用雜湊表預處理，單次查詢可以很快，但建表需要 O(n) 時間和空間；它只適合同一個靜態陣列的大量 查詢，而且會浪費輸入已經有序的條件。
第六步：用邊界與隨機差分驗證。
至少涵蓋：
| 輸入 | target | 預期 | |---|---:|---:| | [] | 1 | [-1, -1] | | [5] | 5 | [0, 0] | | [5] | 4 | [-1, -1] | | [1, 2, 2, 2, 3] | 2 | [1, 3] | | [2, 2] | 2 | [0, 1] | | [1, 2, 3] | 0 | [-1, -1] | | [1, 2, 3] | 4 | [-1, -1] |
再隨機產生含重複值的排序陣列，把結果和線性基準 indexOf、lastIndexOf 比較。線性方法不符合目標複雜度， 卻很適合作為測試 oracle。固定案例檢查已知邊界，隨機差分更容易暴露只在特定重複長度或端點發生的錯誤。
高品質示範回答
「陣列已經按非遞減順序排列，而且要求 O(log n)，所以我不會先找到一個目標再向兩側掃描，因為全是重複值 時會退化成線性時間。我把答案定義成兩個插入點：第一個大於等於目標的位置，以及第一個嚴格大於目標的位置。
兩個搜尋都使用半開區間 [left, right)。找左邊界時，迴圈保持 left 左側都小於目標，right 及其右側 都大於等於目標。若中點值小於目標，答案只能在右側，令 left = middle + 1；否則中點仍可能是答案， 令 right = middle。結束時兩者相等，就是 lower bound。upper bound 只把條件改成中點值小於等於目標時 向右移動。
我先求 lower bound。如果它等於陣列長度，或對應元素不等於目標，就回傳 [-1, -1]。否則右邊界是 upper bound 減一。這樣空陣列、目標不存在、全部重複以及目標位於首尾都使用同一套邏輯。
每次迴圈把區間減半，做兩次仍是 O(log n)，只用常數索引，所以空間 O(1)。我會用固定邊界案例，再用 隨機排序陣列和 indexOf、lastIndexOf 做差分測試。實作中不使用 target + 1，避免建立約束域外的 哨兵值，也讓邊界定義適用於其他有序比較域。」
常見錯誤
- 找到任意目標後向兩邊掃描 → 全部元素相同時退化為
O(n)→ 分別二分 lower bound 與 upper bound。 - 相等時立即回傳 → 回傳的是任意命中，不保證首尾位置 → 相等時繼續保留可能包含邊界的一半。
- 把
right初始化為陣列長度卻存取nums[right]→ 半開區間右端不可存取 → 只存取middle，迴圈到左右相等。 - 更新為
left = middle→ 兩元素區間可能永遠不縮小 → 排除中點時使用middle + 1。 - 目標不存在時直接回傳插入點 → 插入位置不等於命中位置 → 檢查越界和
nums[first] !== target。 - 用
target + 1求右邊界 → 依賴約束域外或不存在的後繼值 → 直接實作第一個嚴格大於目標的位置。 - 混用閉區間與半開區間模板 → 初始化、迴圈條件和更新規則互相衝突 → 先寫區間語意和不變量，再寫程式。
- 只測試中間有多個重複值 → 空陣列、端點和未命中仍可能錯誤 → 加入邊界表和隨機差分測試。
- 宣稱排序後再二分仍是
O(log n)→ 排序本身至少主導總成本 → 使用題目已排序前提，未排序時重新計算複雜度。
追問與應對
追問一：如果只需要判斷目標是否存在，還需要兩次二分嗎？
不需要。執行一次 lower bound，再檢查位置是否越界且值等於目標即可，仍是 O(log n)。如果標準函式庫提供 契約明確的二分搜尋，也可以直接使用。兩次搜尋只為同時取得重複區間的左右邊界。
追問二：如何回傳目標值出現的次數？
若目標存在，次數是 upperBound - lowerBound；不存在時兩個插入點相等，差也是 0。因此只計算次數時甚至 不需要另外讀取陣列元素。這個公式來自兩個邊界之間恰好都是等於目標的元素。
追問三：如果陣列按降序排列怎麼辦？
不變量和比較方向都要反轉。降序 lower bound 可以定義為第一個小於等於目標的位置，另一邊界是第一個嚴格 小於目標的位置。不能只把最終陣列倒序理解而保留原比較條件；更穩妥的方式是先寫清楚分割述詞，再依述詞真假 更新區間。
追問四：如果元素是物件，要按某個欄位查找怎麼辦？
把比較值抽成已排序的鍵，例如按 createdAt 排序就比較該欄位。若鍵提取昂貴且會重複查詢，可預先保存鍵 陣列；Python 官方文件也建議在迴圈查詢中快取或預先計算鍵。前提是物件序列在搜尋期間不能被修改，否則有序 不變量失效。
追問五：如果資料不在記憶體，而在支援有序索引的資料庫中呢？
不要把應用層二分翻譯成多次遠端查詢。讓資料庫索引處理範圍定位，例如查詢等於目標的最小和最大穩定排序鍵， 或使用有序索引的起止掃描。應用層每輪一次網路往返會把 O(log n) 比較變成多次高延遲請求，也可能在並行 寫入下觀察到不同快照。
追問六：如何把這個模板推廣到「最小可行答案」問題？
先找到一個單調述詞，例如容量 x 以下不可行、從某個位置開始都可行，然後用 lower bound 搜尋第一個 述詞為真的位置。此時陣列元素可以是隱式答案空間，nums[middle] < target 被替換為 !feasible(middle)。 必須先證明述詞只有一次從假變真；若真假交替，二分搜尋沒有正確性基礎。