LeetCode 35 搜索插入位置：二分查找邊界條件完美處理

題目描述

給定一個已排序且無重復元素的整數數組 nums 和一個目標值 target，若目標值存在返回其索引；否則返回它將會被按順序插入的位置。要求時間複雜度 O(log n)。

核心思路：標準二分查找變體

本質是尋找第一個大於等於 target 的元素位置 (lower_bound)。

關鍵邊界條件

1. 目標值小於所有元素 → 返回 0
2. 目標值大於所有元素 → 返回 n (數組長度)
3. 目標值在中間 → 返回第一個 ≥ target 的索引

優雅的二分實現

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int n = nums.size();
        int left = 0, right = n; // [left, right) 左閉右開區間
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1; // 目標在右半區間
            } else {
                right = mid;    // 目標在左半區間 (含 mid)
            }
        }
        return left; // left == right 為插入位置
    }
};

為什麼這樣寫最優雅？

步驟演示

nums = [1,3,5,6], target = 5
left=0, right=4
mid=2, nums[2]=5 ≥ 5 → right=2
mid=1, nums[1]=3 < 5  → left=2
left==right==2 → return 2 ✓

nums = [1,3,5,6], target = 2
left=0, right=4
mid=2, nums[2]=5 ≥ 2 → right=2
mid=1, nums[1]=3 ≥ 2 → right=1
mid=0, nums[0]=1 < 2  → left=1
left==right==1 → return 1 ✓

nums = [1,3,5,6], target = 7
left=0, right=4
mid=2, 5<7 → left=3
mid=3, 6<7 → left=4
left==right==4 → return 4 ✓ (插入末尾)

複雜度分析

• 時間：O(log n) - 標準二分查找
• 空間：O(1) - 僅使用常數額外空間

STL 一行解法 (面試加分項)

return lower_bound(nums.begin(), nums.end(), target) - nums.begin();

lower_bound 正是標準庫實現的「第一個不小於 value 的迭代器」，完美契合本題。

常見錯誤避坑

1. 區間定義不一致：混用 [left, right] 和 [left, right) 導致邊界錯誤。
2. 死循環：mid = (left+right)/2 配合 left = mid 而非 left = mid+1。
3. 溢出：大數組下 left+right 超過 INT_MAX。
4. 忽略「插入末尾」情況：right 初始值應為 n 而非 n-1。

本題是二分查找「下界」問題的教科書級範例，掌握左閉右開區間寫法，可舉一反三解決 upper_bound、first_bad_version 等同類問題。