LeetCode 35 搜索插入位置：二分查找經典應用

題目大意

給定升序無重複數組和目標值，返回目標值索引；若不存在，返回按順序插入的位置索引。

二分查找核心

尋找第一個 ≥ target 的位置。若找到等於 target 則為其索引；否則插入位置即為該位置。標準庫 lower_bound 完美契合。

一行代碼解法

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
    }
};

手寫二分邏輯

int searchInsert(vector<int>& nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l <= r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return l; // l 即為第一個 ≥ target 的位置
}

總結

掌握 lower_bound 語義，二分查找模板靈活應用於插入位置、區間查找等變體問題。