LeetCode 35 搜索插入位置 Search Insert Position 五种解法全剖析从线性扫描到二分下界NeetCode 仓库多语言实战【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以仓库 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大于数组中所有元素应插入到末尾。算法步骤遍历数组中的每个下标i若nums[i] target直接返回i若循环结束仍未返回返回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(vectorint 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: Veci32, 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并继续向左搜索看是否存在更小的合法下标。算法步骤初始化res n默认插入点在末尾左右指针l 0、r n - 1当l r时循环计算mid (l r) / 2若nums[mid] target直接返回mid若nums[mid] target令res mid并向左搜索r mid - 1否则向右搜索l mid 1返回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 respublic 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(vectorint 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: Veci32, 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变量。算法步骤初始化指针l 0、r n - 1当l r时循环计算mid (l r) / 2若nums[mid] target返回mid若nums[mid] target向左搜索r mid - 1否则向右搜索l mid 1返回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 lpublic 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(vectorint 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: Veci32, 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这是该模板能够处理插入到末尾这一边界情况的关键。算法步骤初始化指针l 0、r n注意r从n开始而非n - 1当l r时循环计算m l (r - l) / 2用该写法而非(l r) / 2可避免大数相加溢出若nums[m] target令r m否则令l m 1返回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 lpublic 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(vectorint 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: Veci32, 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大多数语言都提供了内置的二分查找或下界函数它们要么直接返回目标值所在下标要么返回为维持有序应插入的位置。直接调用这些函数可以避免重复实现二分查找代码量最小也最不容易写错边界。算法步骤调用语言内置二分查找函数例如 Python 的bisect_left、C 的lower_bound、Java 的Arrays.binarySearch若函数返回负值Java按-index - 1换算为插入点返回换算后的下标。多语言实现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(vectorint 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: Veci32, target: i32) - i32 { match nums.binary_search(target) { Ok(i) i as i32, Err(i) i as i32, } } }内置函数行为解读不同语言内置函数返回值的约定不同理解这一点是正确使用的关键Pythonbisect.bisect_left(nums, target)直接返回第一个大于等于target的下标正是本题答案无需任何换算。Clower_bound返回指向第一个大于等于target的迭代器减去begin()即得下标C 没有独立的未找到信号lower_bound天然就是插入点语义。JavaArrays.binarySearch找到时返回非负下标未找到时返回-(insertion point) - 1所以换算公式是-index - 1。C#Array.BinarySearch未找到时返回插入点的按位取反补码因此换算公式是~idx等价于-idx - 1。Gosort.SearchInts(nums, target)与 Python 的bisect_left等价直接返回第一个大于等于target的下标。KotlinIntArray.binarySearch未找到时返回-(insertion point) - 1换算为-(idx 1)。Rustslice::binary_search返回ResultOk(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显式resl rr mid - 1/l mid 1res$O(\log n)$$O(1)$二分 II返回ll rr mid - 1/l mid 1l$O(\log n)$$O(1)$下界二分l rr初始为nr m/l m 1l$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.pylow, 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.cppleft rightright 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分支但算法内核完全一致——阅读时抓住循环条件 指针更新 返回值三要素就能在不同写法之间自如切换。建议以解法四的下界模板为主力记忆点因为它同时也是 Clower_bound、Gosort.SearchInts、Rustbinary_search内部语义的统一抽象。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考