35. Search Insert Position

Search Insert Position

題目描述：給定一個排序好的整數陣列 nums 以及一個目標值 target，找到 target 在陣列中的索引。若 target 不存在，則回傳它應被插入的位置（使陣列保持有序）。

解題思路：這是二分搜尋的經典應用。維護左右指標 lo = 0、hi = nums.size() - 1，每次計算中點 mid：

• 若 nums[mid] == target，直接回傳 mid。
• 若 nums[mid] < target，目標在右半邊，lo = mid + 1。
• 若 nums[mid] > target，目標在左半邊，hi = mid - 1。

迴圈結束後，lo 就是 target 應被插入的位置。這是因為當迴圈終止時，lo > hi，lo 指向第一個大於 target 的元素位置，即正確的插入點。

時間複雜度：O(log n) — 每次迭代將搜尋範圍縮減一半，最多執行 log₂(n) 次比較。

空間複雜度：O(1) — 只使用常數個指標變數，不需要額外空間。

方法一：線性掃描 從左到右遍歷陣列，找到第一個大於或等於 target 的位置即為答案。時間複雜度 O(n)，適合小型輸入，但效率不如二分搜尋。

方法二：lower_bound 標準庫函式 直接使用 C++ STL 的 std::lower_bound(nums.begin(), nums.end(), target)，它內部實現即為二分搜尋，回傳第一個 ≥ target 的迭代器，轉換為索引即可。時間複雜度同為 O(log n)，寫法更簡潔但需熟悉 STL。

1. 若陣列中有重複元素且 target 出現多次，你的做法會回傳哪個索引？如何保證一定回傳最左邊的位置？
2. 如果陣列未排序，你會先排序再搜尋，還是有其他策略？排序後插入的整體時間複雜度是多少？
3. 這題的 lo 在迴圈結束後正好是插入點，你能用數學歸納法證明這個不變量（invariant）嗎？