LeetCode 35. Search Insert Position 题解：Go 实现有序数组的二分搜索插入位置

LeetCode 35. Search Insert Position 题解Go 实现有序数组的二分搜索插入位置【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文以 LeetCode 35. Search Insert Position 为核心讲解如何在已排序且无重复元素的数组中用 O(log n) 的二分查找快速定位目标值若目标不存在则返回它应当被插入的位置。该题是二分搜索最经典的变种之一本文不仅完整复现题目与示例还结合仓库内 Go 实现源码 与配套测试用例逐行推演算法原理、边界处理并与标准二分查找LeetCode 704做对比。读完本文你将掌握“找最后一个小于 target 的元素”这类二分变种的通用写法并了解本仓库的测试组织方式。题目描述Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.You may assume no duplicates in the array.给定一个有序数组和一个目标值如果在数组中找到目标值返回其索引如果目标值不在数组中返回它按顺序插入后应处的位置。题目明确保证数组中没有重复元素这简化了插入位置的判定——不存在“相同值应插在哪个重复项前后”的歧义。示例示例 1Input: [1,3,5,6], 5 Output: 2目标值 5 存在于数组中直接返回其下标 2。示例 2Input: [1,3,5,6], 2 Output: 12 不在数组中按序应插在下标 1 处位于 1 与 3 之间。示例 3Input: [1,3,5,6], 7 Output: 47 大于数组中所有元素插入位置在数组末尾返回len(nums) 4。示例 4Input: [1,3,5,6], 0 Output: 00 小于数组中所有元素插入位置在数组头部返回 0。题目大意给定一个已经从小到大排序好的数组要求在数组中找到插入 target 元素的位置命中则返回原下标未命中则返回插入后的下标。你可以假设数组中无重复元素。解题思路本题是经典的二分搜索变种题在有序数组中找到最后一个比 target 小的元素的位置答案就是该位置 1若数组中所有元素都不小于 target即第一个元素就已经 ≥ target则答案为 0。用二分法将搜索区间不断对半收缩每次通过比较中间元素nums[mid]与target的大小关系来决定向左还是向右收窄最终在 O(log n) 时间内收敛到答案时间复杂度远优于线性扫描的 O(n)。源码实现与逐行推演仓库在 leetcode/0035.Search-Insert-Position/35. Search Insert Position.go 中给出了如下实现func searchInsert(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low (high-low)1 if nums[mid] target { high mid - 1 } else { if (mid len(nums)-1) || (nums[mid1] target) { return mid 1 } low mid 1 } } return 0 }逐行解读初始化区间low, high : 0, len(nums)-1二分查找的经典闭区间[low, high]初始化。当nums为空len(nums) 0时high -1循环体不会执行直接落入最后的return 0恰好对应空数组插入位置为 0 的正确结果。循环条件low high采用闭区间写法与 LeetCode 704 标准二分查找见后文对比保持一致low high时仍需再判断一次中点。中点防溢出写法mid : low (high-low)1等价于(lowhigh)/2但避免了low high在极端大数组下可能产生的整数溢出同时用右移一位代替除以 2属于 Go 社区常见的高效写法。分支一nums[mid] target当中点值大于等于目标时说明答案区间应在中点的左侧含 mid 本身可能作为第一个 ≥ target 的位置于是high mid - 1向左收窄。注意这里用的是而非因为本题关心的是“第一个不小于 target 的位置”命中值的情况也会向左收缩最终通过“最后一个小于 target 的元素位置 1”统一得出答案。分支二nums[mid] target中点值小于目标说明答案只可能在中点右侧。此时先做一次命中检测若mid len(nums)-1即中点是数组最后一个元素说明整个数组都小于 target插入位置就是数组末尾mid 1若nums[mid1] target说明mid正好是最后一个小于 target 的元素插入位置即mid 1两种情况命中其一直接return mid 1。继续收窄若mid1仍然小于 target说明最后一个小于 target 的元素还在更右侧执行low mid 1继续二分。兜底return 0循环正常退出low high说明区间被完全耗尽且过程中从未出现nums[mid] target的情况即整个数组都 ≥ target插入位置为 0。核心不变量整个算法维护的不变量是low左侧含 low 之前的已排除区的元素都小于 targethigh右侧含 high 之后的已排除区的元素都大于等于 target。循环结束时low恰好指向第一个大于等于 target 的位置——这正是“插入位置”的定义因此该写法在语义上与标准lower_bound下界查找完全等价。边界情况分析场景数组target预期输出代码路径命中中间值[1,3,5,6]52二分命中nums[mid] target持续收窄后经nums[mid1] target返回插入区间中间[1,3,5,6]21经nums[mid1] target命中返回mid 1插入数组末尾[1,3,5,6]74经mid len(nums)-1命中返回末尾下标 1插入数组头部[1,3,5,6]00全程nums[mid] target循环耗尽后兜底返回 0空数组[]任意值0循环不执行兜底返回 0单元素数组[5]50mid 0nums[mid] target成立循环耗尽返回 0单元素数组[5]30nums[mid] target成立返回 0单元素数组[5]81mid len(nums)-1命中返回 1从上面的推演可以看出由于nums[mid] target分支会在low high时继续执行一次并将high左移循环最终以low high退出并返回 0恰好覆盖“整个数组都不小于 target”的场景而“整个数组都小于 target”的场景则由mid len(nums)-1的显式判断在循环内提前返回两种极端情况都被精确处理。与标准二分查找LeetCode 704的对比本仓库同时收录了标准二分查找 704. Binary Search 的 Go 实现func search704(nums []int, target int) int { low, high : 0, len(nums)-1 for low high { mid : low (high-low)1 if nums[mid] target { return mid } else if nums[mid] target { high mid - 1 } else { low mid 1 } } return -1 }两者结构高度相似相同的闭区间初始化、相同的防溢出中点写法、相同的low high循环条件关键差异在于704 是精确查找nums[mid] target直接返回找不到返回 -1。它只关心“目标在不在”。35 是下界查找lower_bound不区分命中与未命中统一返回“第一个 ≥ target 的下标”。命中时该下标就是元素本身的位置未命中时就是插入位置。因此 35 号题永远有合法答案不会返回 -1。理解这一差异后可以把 35 号题的写法当作一个通用模板凡是“在有序数组中找第一个满足某条件的位置”类问题如插入位置、求下界都可以用nums[mid] target收窄右边界、最后返回low的变体解决。测试用例验证仓库为本题提供了配套测试文件 35. Search Insert Position_test.go采用本仓库一贯的“结构体组织测试数据 循环执行”风格定义question35结构体组合para35输入nums、target与ans35期望输出one在Test_Problem35中一次覆盖四个用例qs : []question35{ {para35{[]int{1, 3, 5, 6}, 5}, ans35{2}}, {para35{[]int{1, 3, 5, 6}, 2}, ans35{1}}, {para35{[]int{1, 3, 5, 6}, 7}, ans35{4}}, {para35{[]int{1, 3, 5, 6}, 0}, ans35{0}}, }这四个用例与本文开头 README 中的四个示例一一对应覆盖了“命中 / 插入中间 / 插入末尾 / 插入头部”四类典型场景。运行方式如下# 单独运行本题测试 go test -v ./leetcode/ -run Test_Problem35如需验证整个仓库的覆盖率项目在 gotest.sh 中统一使用-covermodeatomic生成coverage.txtgo test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...复杂度分析时间复杂度O(log n)。每轮循环将搜索区间减半n为数组长度二分收敛至多执行 log₂(n) 次比较。空间复杂度O(1)。仅使用low、high、mid三个整数变量无额外数据结构原地完成搜索。总结LeetCode 35 是二分查找从“精确查找”迈向“边界查找”的经典进阶题。本文基于仓库 题目 README 的原始描述完整梳理了题目语义有序无重复数组中命中返回下标、未命中返回插入位置核心思路找最后一个小于 target 的元素其位置 1 即答案仓库 Go 实现 的逐行推演与全部边界场景与 704 标准二分 的差异对比配套测试 的用例覆盖与运行方式。掌握本题的lower_bound思路后可以顺带解决一系列同类问题如python中的bisect_left语义、C 的std::lower_bound行为是算法面试中性价比极高的基础模板。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考