演算法面試：如何用二分搜尋第 k 個缺失正整數？

面試官考察點

題目表面是陣列計數，核心是把「到位置 i 為止缺了多少」寫成單調謂詞，再把第 k 個缺失值轉成邊界搜尋。LeetCode 1539 提供嚴格遞增正整數陣列和第 k 個缺失值的公開題面，並提供 Amazon 題組入口；Amazon SDE 指引強調可執行、健壯、經過測試的程式與邊界檢查。來源支持準備價值，不代表任何公司固定面試頻率。

• 能否先寫出 missing(i) = arr[i] - i - 1。
• 能否證明缺失數量隨 i 單調不減。
• 能否處理答案在最後一個元素之後。
• 能否比較線性、二分和列舉生成方案的適用邊界。

30 秒回答框架

先說明陣列從 0 下標開始。位置 i 前包含 arr[i] 個正整數，實際出現 i+1 個，因此缺失數量是 arr[i] - i - 1。對最小下標做二分，尋找第一個滿足 missing(i) >= k 的位置 i。若找到，答案是 k 加上它前面已有的 i 個陣列元素，即 k + i；若整個陣列的缺失數都小於 k，答案在陣列末端之後，直接回傳 k + n。掃描是 O(n)，二分是 O(log n)，額外空間 O(1)。

回答前需要釐清的問題

1. 陣列是否保證嚴格遞增且只包含正整數？若不保證，需要排序或去重，複雜度會改變。
2. k 是否為正整數，是否可能大於陣列長度或整數範圍？
3. 只需要一個第 k 個值，還是要回傳所有缺失值？後者不應硬套二分。
4. 輸入是否可能有超大整數，語言中的加法和索引是否會溢位？
5. 是否要求原陣列不修改？二分方案不修改陣列。

分步驟深入解答

第一步：建立缺失數量公式

如果陣列完全連續，arr[i] 應等於 i + 1。實際值比期望值多出的部分，就是 [1, arr[i]] 中缺失的正整數數量：

missing(i) = arr[i] - (i + 1)
           = arr[i] - i - 1

例如 arr = [2, 3, 4, 7, 11]，在 i=3 時 missing(3) = 7 - 3 - 1 = 3，缺失的是 1、5、6。

第二步：利用單調性定位邊界

陣列嚴格遞增，所以 arr[i+1] >= arr[i] + 1。因此 missing(i+1) >= missing(i)，缺失數量不會下降。二分尋找第一個 missing(i) >= k 的位置；這個位置左邊缺失不足 k，位置本身及右側至少包含 k 個缺失值。

第三步：從邊界反推答案

設邊界為 i。i 左側有 i 個陣列元素，且這些元素之前的缺失數量小於 k。答案等於 k 加上需要跨過的 i 個已出現元素：k + i。若邊界不存在，整個陣列最後的缺失數量仍小於 k，答案在陣列後方，n 個陣列元素都要跨過，所以是 k + n。

第四步：給出二分實作

function findKthPositive(arr: number[], k: number): number {
  let left = 0;
  let right = arr.length;

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const missing = arr[mid] - mid - 1;
    if (missing < k) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return k + left;
}

這裡 right 取 n，表示邊界可以落在陣列末端之後。迴圈結束時 left 是第一個缺失數達到 k 的位置，統一回傳 k + left，不需另外分支。

第五步：證明複雜度與測試邊界

每次二分把搜尋區間縮半，時間複雜度 O(log n)，只使用常數變數。測試應包括 arr = [1,2,3,4], k = 2 得到 6，arr = [2,3,4,7,11], k = 5 得到 9，缺失從 1 開始、陣列末尾連續、k=1，以及單元素陣列。還應驗證公式不依賴特定語言的整數下標細節。

高品質示範回答

我會先定義下標 i 處已經缺了多少個正整數：arr[i] - i - 1。因為陣列嚴格遞增，這個數量單調不減，所以可以二分尋找第一個缺失數不少於 k 的位置。若邊界是 i，前面有 i 個已出現元素，因此第 k 個缺失值是 k + i；把右邊界設為 n，就能自然處理答案在陣列最大值之後的情況。

實作使用半開區間 [left, right)。當 missing(mid) 小於 k 時，邊界一定在右側；否則收縮到 mid。迴圈結束回傳 k + left。複雜度是 O(log n) 時間和 O(1) 空間。最後用首項缺失、尾部缺失、連續陣列、單元素和多個 k 值測試，並與線性掃描結果對拍。

常見錯誤

• 把缺失數量寫成 arr[i] - i，少減了 1。
• 二分尋找最後一個小於 k 的位置，卻忘記把答案公式改成對應邊界。
• 把 right 設為 n - 1，導致答案在陣列末端之後時需要額外分支且容易越界。
• 陣列不滿足嚴格遞增時仍直接套公式。
• 只測題面樣例，沒有測試 [1,2,3]、[2] 和尾部連續等邊界。
• 聲稱二分一定比掃描快，卻不說明 n 很小時的常數開銷和輸入是否已排序。

實作取捨

依資料規模與邊界要求選擇線性掃描或二分方案，並用測試驗證不變量。

追問及應對

為什麼缺失數量是單調的？

嚴格遞增保證下一個元素至少比前一個大 1。下標增加 1 時，實際值增加至少 1，所以 arr[i] - i - 1 不會下降。

如果陣列未排序或有重複值怎麼辦？

先按新契約處理：排序、去重並確認只保留正整數。排序成本至少 O(n log n)，去重後再使用同一個缺失數量公式；不能把原題 O(log n) 結論直接帶到未排序輸入。

什麼時候線性掃描更合適？

陣列很短、只需一次答案，或輸入來自串流且無法隨機存取時，掃描更簡單。面試中應說明二分依賴已排序陣列和 O(1) 隨機存取。

如何回傳前 k 個缺失值？

先用邊界公式找到值域起點，再按陣列指標和目前候選值線性生成；輸出本身就需要 O(k) 時間，不能把輸出成本藏在 O(log n) 裡。

k 或 arr[i] 很大時怎麼防止溢位？

使用語言提供的安全整數型別或 64 位元整數，檢查 k + left 和 arr[i] - i - 1 的範圍。若業務允許任意大整數，介面和測試應明確 BigInt 或等價表示。

評分標準

能從計數公式推導單調謂詞、給出半開區間實作並解釋答案公式，可評為強通過；若只會背程式碼、無法證明邊界，應繼續追問。