LeetCode 35 搜索插入位置 Search Insert Position 五种解法全剖析：从线性扫描到二分下界（NeetCode 仓库多语言实战）

本篇技术指南以仓库 articles/search-insert-position.md 为核心骨架，完整梳理 LeetCode 0035「搜索插入位置」的五种解法：线性扫描、两种显式/隐式记录插入点的二分查找、经典下界（lower bound）二分以及各语言内置二分函数，并逐一给出 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的实现。读完本文，你不仅能独立写出本题的标准解，还能理解 l <= r 与 l < r 两套边界约定的本质区别，并在实际面试中快速套用"求第一个大于等于 target 的位置"这一通用模板。文末还将对照本仓库 python、cpp、go、rust 等 12 个语言的真实提交，说明仓库中的实现分别对应哪种变体。

前置知识（Prerequisites）

在着手解决本题之前，需要具备以下基础能力：

• 数组（Arrays）：能够按索引遍历并访问数组元素，理解数组下标从 0 开始、长度为 n 时合法下标范围为 [0, n-1]。
• 二分查找（Binary Search）：知道如何通过在有序数组中反复对半收缩搜索区间来高效定位目标值。本题正是"二分查找边界变体"最典型的入门训练题，也是 NeetCode 二分查找分类下的基础题（见 README.md 的 Binary Search 分类）。

问题定义

给定一个按升序排列、元素互不相同的整数数组 nums 和一个目标值 target，要求返回 target 在数组中的下标；如果 target 不存在，则返回它应当被插入以保持数组有序的位置。也就是说，返回值等价于第一个大于等于 target 的元素的下标，若所有元素都小于 target，则返回 n（数组长度，即插到末尾）。

---

解法一：线性扫描（Linear Search）

思路（Intuition）

从左到右扫描整个数组，寻找第一个大于等于 target 的元素。一旦找到，该下标就是 target 存在或应被插入的位置；如果遍历完都没有找到符合条件的元素，说明 target 大于数组中所有元素，应插入到末尾。

算法步骤

1. 遍历数组中的每个下标 i；
2. 若 nums[i] >= target，直接返回 i；
3. 若循环结束仍未返回，返回 n（数组长度，表示插入到末尾）。

多语言实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for i in range(len(nums)):
            if nums[i] >= target:
                return i
        return len(nums)

public class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.size();
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    searchInsert(nums, target) {
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.Length;
    }
}

func searchInsert(nums []int, target int) int {
    for i := 0; i < len(nums); i++ {
        if nums[i] >= target {
            return i
        }
    }
    return len(nums)
}

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        for (i in nums.indices) {
            if (nums[i] >= target) {
                return i
            }
        }
        return nums.size
    }
}

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        for i in 0..<nums.count {
            if nums[i] >= target {
                return i
            }
        }
        return nums.count
    }
}

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        for i in 0..nums.len() {
            if nums[i] >= target {
                return i as i32;
            }
        }
        nums.len() as i32
    }
}

复杂度分析

• 时间复杂度：$O(n)$，最坏情况下需要扫描整个数组。
• 空间复杂度：$O(1)$ 额外空间。

---

解法二：二分查找 I（显式维护候选插入点）

思路（Intuition）

由于数组已经有序，可以使用二分查找在对数时间内定位目标。核心技巧是显式维护一个"当前最佳插入点"变量 res：每当发现一个元素大于 target 时，就更新 res 并继续向左搜索，看是否存在更小的合法下标。

算法步骤

1. 初始化 res = n（默认插入点在末尾），左右指针 l = 0、r = n - 1；
2. 当 l <= r 时循环：
   • 计算 mid = (l + r) / 2；
   • 若 nums[mid] == target，直接返回 mid；
   • 若 nums[mid] > target，令 res = mid 并向左搜索：r = mid - 1；
   • 否则向右搜索：l = mid + 1；
3. 返回 res（最终的插入位置）。

多语言实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        res = len(nums)
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                res = mid
                r = mid - 1
            else:
                l = mid + 1
        return res

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int res = nums.length;
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
}

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int res = nums.size();
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    searchInsert(nums, target) {
        let res = nums.length;
        let l = 0,
            r = nums.length - 1;
        while (l <= r) {
            const mid = Math.floor((l + r) / 2);
            if (nums[mid] === target) {
                return mid;
            }
            if (nums[mid] > target) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return res;
    }
}

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int res = nums.Length;
        int l = 0, r = nums.Length - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return res;
    }
}

func searchInsert(nums []int, target int) int {
    res := len(nums)
    l, r := 0, len(nums)-1
    for l <= r {
        mid := (l + r) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[mid] > target {
            res = mid
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return res
}

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        var res = nums.size
        var l = 0
        var r = nums.size - 1
        while (l <= r) {
            val mid = (l + r) / 2
            if (nums[mid] == target) {
                return mid
            }
            if (nums[mid] > target) {
                res = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return res
    }
}

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var res = nums.count
        var l = 0
        var r = nums.count - 1
        while l <= r {
            let mid = (l + r) / 2
            if nums[mid] == target {
                return mid
            }
            if nums[mid] > target {
                res = mid
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return res
    }
}

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let mut res = nums.len() as i32;
        let (mut l, mut r) = (0i32, nums.len() as i32 - 1);
        while l <= r {
            let mid = (l + r) / 2;
            if nums[mid as usize] == target {
                return mid;
            }
            if nums[mid as usize] > target {
                res = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        res
    }
}

复杂度分析

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$ 额外空间。

---

解法三：二分查找 II（循环结束后 l 就是答案）

思路（Intuition）

一个更简洁的观察：当二分查找在没有找到目标值的情况下结束时，左指针 l 恰好落在正确的插入位置。原因在于 l 总是会越过所有小于 target 的元素，最终停在 target 应该插入的地方，无需额外的 res 变量。

算法步骤

1. 初始化指针 l = 0、r = n - 1；
2. 当 l <= r 时循环：
   • 计算 mid = (l + r) / 2；
   • 若 nums[mid] == target，返回 mid；
   • 若 nums[mid] > target，向左搜索：r = mid - 1；
   • 否则向右搜索：l = mid + 1；
3. 返回 l 作为插入下标。

多语言实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] > target:
                r = mid - 1
            else:
                l = mid + 1
        return l

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    searchInsert(nums, target) {
        let l = 0,
            r = nums.length - 1;
        while (l <= r) {
            const mid = Math.floor((l + r) / 2);
            if (nums[mid] === target) {
                return mid;
            }
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int l = 0, r = nums.Length - 1;

        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        return l;
    }
}

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums)-1
    for l <= r {
        mid := (l + r) / 2
        if nums[mid] == target {
            return mid
        }
        if nums[mid] > target {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return l
}

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        var l = 0
        var r = nums.size - 1
        while (l <= r) {
            val mid = (l + r) / 2
            if (nums[mid] == target) {
                return mid
            }
            if (nums[mid] > target) {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return l
    }
}

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var l = 0
        var r = nums.count - 1
        while l <= r {
            let mid = (l + r) / 2
            if nums[mid] == target {
                return mid
            }
            if nums[mid] > target {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
        return l
    }
}

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let (mut l, mut r) = (0i32, nums.len() as i32 - 1);
        while l <= r {
            let mid = (l + r) / 2;
            if nums[mid as usize] == target {
                return mid;
            }
            if nums[mid as usize] > target {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        l
    }
}

复杂度分析

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$ 额外空间。

---

解法四：二分查找（下界 Lower Bound）

思路（Intuition）

这是经典的下界（lower bound）算法：找到第一个大于等于 target 的元素的最小下标。通过把循环条件写成 l < r，并在 nums[m] >= target 时令 r = m，搜索区间会不断收敛到下界位置，无需单独的返回值变量。注意这里的 r 初始化为 n 而不是 n - 1，这是该模板能够处理"插入到末尾"这一边界情况的关键。

算法步骤

1. 初始化指针 l = 0、r = n（注意：r 从 n 开始，而非 n - 1）；
2. 当 l < r 时循环：
   • 计算 m = l + (r - l) / 2（用该写法而非 (l + r) / 2，可避免大数相加溢出）；
   • 若 nums[m] >= target，令 r = m；
   • 否则令 l = m + 1；
3. 返回 l（下界位置）。

多语言实现

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums)
        while l < r:
            m = l + ((r - l) // 2)
            if nums[m] >= target:
                r = m
            elif nums[m] < target:
                l = m + 1
        return l

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    searchInsert(nums, target) {
        let l = 0,
            r = nums.length;
        while (l < r) {
            let m = l + Math.floor((r - l) / 2);
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int l = 0, r = nums.Length;

        while (l < r) {
            int m = l + (r - l) / 2;
            if (nums[m] >= target) {
                r = m;
            } else {
                l = m + 1;
            }
        }

        return l;
    }
}

func searchInsert(nums []int, target int) int {
    l, r := 0, len(nums)
    for l < r {
        m := l + (r-l)/2
        if nums[m] >= target {
            r = m
        } else {
            l = m + 1
        }
    }
    return l
}

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        var l = 0
        var r = nums.size
        while (l < r) {
            val m = l + (r - l) / 2
            if (nums[m] >= target) {
                r = m
            } else {
                l = m + 1
            }
        }
        return l
    }
}

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var l = 0
        var r = nums.count
        while l < r {
            let m = l + (r - l) / 2
            if nums[m] >= target {
                r = m
            } else {
                l = m + 1
            }
        }
        return l
    }
}

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        let (mut l, mut r) = (0usize, nums.len());
        while l < r {
            let m = l + (r - l) / 2;
            if nums[m] >= target {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l as i32
    }
}

复杂度分析

• 时间复杂度：$O(\log n)$。
• 空间复杂度：$O(1)$。

---

解法五：使用语言内置二分函数

思路（Intuition）

大多数语言都提供了内置的二分查找或下界函数，它们要么直接返回目标值所在下标，要么返回"为维持有序应插入的位置"。直接调用这些函数可以避免重复实现二分查找，代码量最小，也最不容易写错边界。

算法步骤

1. 调用语言内置二分查找函数（例如 Python 的 bisect_left、C++ 的 lower_bound、Java 的 Arrays.binarySearch）；
2. 若函数返回负值（Java），按 -index - 1 换算为插入点；
3. 返回换算后的下标。

多语言实现

import bisect
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return bisect.bisect_left(nums, target)

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int index = Arrays.binarySearch(nums, target);
        return index >= 0 ? index : -index - 1;
    }
}

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

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number}
     */
    searchInsert(nums, target) {
        // There is no built in Binary Search function for JS.
        let index = nums.findIndex((x) => x >= target);
        return index !== -1 ? index : nums.length;
    }
}

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int idx = Array.BinarySearch(nums, target);
        return idx >= 0 ? idx : ~idx;
    }
}

func searchInsert(nums []int, target int) int {
    return sort.SearchInts(nums, target)
}

class Solution {
    fun searchInsert(nums: IntArray, target: Int): Int {
        val idx = nums.binarySearch(target)
        return if (idx >= 0) idx else -(idx + 1)
    }
}

class Solution {
    func searchInsert(_ nums: [Int], _ target: Int) -> Int {
        var l = 0
        var r = nums.count
        while l < r {
            let m = l + (r - l) / 2
            if nums[m] >= target {
                r = m
            } else {
                l = m + 1
            }
        }
        return l
    }
}

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        match nums.binary_search(&target) {
            Ok(i) => i as i32,
            Err(i) => i as i32,
        }
    }
}

内置函数行为解读

不同语言内置函数返回值的约定不同，理解这一点是正确使用的关键：

• Python bisect.bisect_left(nums, target)：直接返回第一个大于等于 target 的下标，正是本题答案，无需任何换算。
• C++ lower_bound：返回指向第一个大于等于 target 的迭代器，减去 begin() 即得下标；C++ 没有独立的"未找到"信号，lower_bound 天然就是插入点语义。
• Java Arrays.binarySearch：找到时返回非负下标；未找到时返回 -(insertion point) - 1，所以换算公式是 -index - 1。
• C# Array.BinarySearch：未找到时返回插入点的按位取反（补码），因此换算公式是 ~idx，等价于 -idx - 1。
• Go sort.SearchInts(nums, target)：与 Python 的 bisect_left 等价，直接返回第一个大于等于 target 的下标。
• Kotlin IntArray.binarySearch：未找到时返回 -(insertion point) - 1，换算为 -(idx + 1)。
• Rust slice::binary_search：返回 Result，Ok(i) 是命中下标，Err(i) 中的 i 恰好就是应插入位置（等价于下界），因此 Ok/Err 两个分支返回同一个 i 即可。
• JavaScript：语言本身没有内置二分查找 API，注释中也明确说明这一点，因此使用 findIndex 线性扫描兜底，这也是解法一在 JS 里的函数式写法。

复杂度分析

• 时间复杂度：$O(\log n)$（findIndex 版本为 $O(n)$）。
• 空间复杂度：$O(1)$。

---

五种解法对比小结

解法	循环条件	指针更新	返回值	时间复杂度	空间复杂度
线性扫描	—	—	首个 >= target 的下标，否则 n	$O(n)$	$O(1)$
二分 I（显式 res）	l <= r	r = mid - 1 / l = mid + 1	res	$O(\log n)$	$O(1)$
二分 II（返回 l）	l <= r	r = mid - 1 / l = mid + 1	l	$O(\log n)$	$O(1)$
下界二分	l < r，r 初始为 n	r = m / l = m + 1	l	$O(\log n)$	$O(1)$
内置函数	—	—	按语言约定换算	$O(\log n)$	$O(1)$

面试与工程实践中最推荐掌握解法四（下界二分）：它是一套可复用的通用模板，能直接迁移到"求第一个大于等于/大于某个值的位置""统计小于某个值的元素个数"等衍生问题。

---

常见陷阱（Common Pitfalls）

陷阱一：二分边界上的 Off-by-One 错误

一个高频错误是使用错误的循环条件或错误的指针更新方式。例如在 l < r 与 l <= r 之间切换时没有同步调整收缩逻辑，可能导致漏掉元素或陷入死循环。同样，在 r = mid 与 r = mid - 1 之间混用，也会造成结果错误或死循环：

• l <= r 模板要求 r = mid - 1（因为 mid 已被检查过，r 是闭区间右边界）；
• l < r 模板要求 r = mid（此时 r 是开区间右边界，mid 本身可能仍是下界候选）。

两种模板的 r 含义不同，千万不要混用。

陷阱二：忘记处理"插入到末尾"的情况

当 target 大于数组中所有元素时，插入位置应为 n（数组长度）。初学者常犯的错误包括：返回 -1、返回越界下标、或者错误地返回最后一个下标。请务必确认你的算法在 target 超过全部元素时正确返回 n：

• 解法一依赖 return len(nums) 兜底；
• 解法二依赖 res 初始值 n；
• 解法三/四依赖 l 在循环结束后自然收敛到 n。

例如 nums = [1, 3, 5, 6], target = 7，正确答案是 4（插入到末尾），这正是解法三、解法四中 l 最终停在 n 的典型场景。

---

仓库源码印证：各语言实现对应哪种变体

本仓库在 README.md 的 Binary Search 分类下列出了 0035 题，并在 12 个语言目录下提供了完整可运行实现。对照本文的五种解法，仓库实际代码恰好覆盖了三种主流变体，可以作为"同一题目不同写法"的对照学习材料：

• 下界二分（解法四）：仓库 python/0035-search-insert-position.py（low, high = 0, len(nums)，high = mid，返回 low）、go/0035-search-insert-position.go、java/0035-search-insert-position.java 均采用该模板，代码注释直接标注 O(log n) and O(1)。
• 返回 l 的二分（解法三）：仓库 cpp/0035-search-insert-position.cpp（left <= right，right = mid - 1，返回 left）与 javascript/0035-search-insert-position.js（命中即返回，未命中返回 left）采用此写法。
• 内置二分（解法五）：仓库 rust/0035-search-insert-position.rs 直接使用 nums.binary_search(&target)，Ok(i) 与 Err(i) 都返回 i，与本文解法五的 Rust 实现完全一致。

此外，仓库还提供了本文未展开代码的其余语言版本，可与上文代码块互相对照：c、csharp、kotlin、ruby、swift、typescript。

最后提醒一点：仓库中的源码与本文章节代码在风格上略有差异（例如仓库 Rust 用 as i32 转换下标、Python 省略了 elif 分支），但算法内核完全一致——阅读时抓住"循环条件 + 指针更新 + 返回值"三要素，就能在不同写法之间自如切换。建议以解法四的下界模板为主力记忆点，因为它同时也是 C++ lower_bound、Go sort.SearchInts、Rust binary_search 内部语义的统一抽象。