二分查找在Go语言里究竟该怎么写才能不出错这个问题我每年面试别人时都会问结果十个人里有八个会写错边界还有两个会在死循环里挣扎半天。说实话二分查找的代码量连二十行都不到但它绝对是最容易翻车的基础算法之一。这篇内容我会从原理讲到实战把我在项目里踩过的边界条件的坑、死循环的坑、还有Go标准库给我们提供的现成方案都梳理一遍并且附上可以直接拿去用的源码和测试方法适合刚学Go的初学者也适合想彻底搞懂二分查找细节的开发者。1. 为什么二分查找看起来简单却总是写不对1.1 核心原理的底层逻辑二分查找的原理一句话就能说完在有序数组中每次拿中间位置的元素和目标值比较根据大小关系排除掉一半的查找范围直到找到目标或者范围为空。听起来完全没难度对吧但是注意一个关键词——有序。这个有序不仅仅指数组本身排好了序更关键的是你必须定义清楚目标值落在哪个区间这个区间本身是闭区间还是开区间。大部分写错二分查找的人问题就出在区间定义始终不统一。我用查字典来打个比方。假设有一本按拼音排序的电话簿你要找王姓。你不会从第一页开始翻你会直接翻到中间看这一页的拼音是在w之前还是之后。如果在w之前说明王字一定在后半本于是你只在后半本里继续翻。这个每次缩小一半查找范围的动作就是二分查找的灵魂。但在代码实现里有个细节很容易被忽略后半本这个范围具体是从哪个下标开始、到哪个下标结束这就是区间边界的问题也是二分查找所有坑的源头。1.2 区间不变量写对二分查找的唯一关键我接触过很多初学者他们写二分查找时最大的问题是同一个代码里一会儿用闭区间一会儿用开区间最后自己都绕晕了。要解决这个问题必须引入一个概念区间不变量。区间不变量可以理解为我给自己定下的规矩——在每一轮循环开始之前我都遵循同一种区间定义。比如你选定了闭区间[left, right]意思就是 left 和 right 都包含在当前查找范围内。那么初始时left 0right n-1整个数组都在范围内。当中间值 nums[mid] 小于目标值时说明目标值在右半部分此时应该把 left 更新为 mid1因为 nums[mid] 已经确认不是目标左边界从 mid 的下一个位置重新开始。当中间值 nums[mid] 大于目标值时说明目标值在左半部分此时 right mid-1同理排除掉 mid。循环条件使用 left right因为当 left right 时当前这一个元素仍然在闭区间内还需要判断一次。另一种写法是半开区间[left, right)也就是 right 本身不包含在查找范围内。这时候初始 right n循环条件就得变成 left right当 nums[mid] 大于目标值时right 可以直接等于 mid因为 mid 本来就不在右边界内。这两种写法都正确但必须在同一份代码里二选一从头到尾保持一致。我在实际教学和 code review 中总结出的经验是闭区间写法对初学者更直观因为所有下标都对应真实存在的元素不容易出现 index out of range半开区间写法在某些变体场景下比如找左边界能让代码更简洁但需要你时刻记得 right 指向的是越界位置。1.3 为什么选 Go 语言来做这个实现既然标题是 Go 语言实现我也顺便聊聊为什么我用 Go 来写二分查找。Go 的切片slice提供了非常自然的下标访问方式而且sort.Search这种标准库函数本身就是二分查找的封装适合做对比验证。另外Go 的int类型在 64 位平台下是 64 位相比 C 语言在计算坐标时不用太担心 int 宽度问题但 mid 的溢出问题仍然存在后面会讲。如果你目前主要用 Python 或 JavaScript二分查找的思路完全一致只是语法糖不同。把本文的代码逻辑搞清楚转换过去是很轻松的事。2. 一份可以放心用的标准实现源码逐行拆解2.1 完整源码展示我直接给出我在实际项目里最常用的一份标准实现它基于闭区间[left, right]循环条件为left rightpackage main import fmt // BinarySearch 在有序切片 data 中查找 target // 如果找到返回对应下标如果找不到返回 -1 func BinarySearch(data []int, target int) int { left, right : 0, len(data)-1 for left right { // 计算中间下标避免 leftright 溢出 mid : left (right-left)1 if data[mid] target { return mid } else if data[mid] target { // 中间值比目标小说明目标在右半部分 left mid 1 } else { // 中间值比目标大说明目标在左半部分 right mid - 1 } } // 循环结束且未返回说明区间已经为空目标不存在 return -1 } func main() { data : []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19} target : 13 index : BinarySearch(data, target) if index ! -1 { fmt.Printf(找到目标 %d下标为 %d\n, target, index) } else { fmt.Printf(未找到目标 %d\n, target) } }上面的代码段可以直接保存为main.go在安装了 Go 环境的机器上运行go run main.go即可看到结果。编译和运行会有如下输出找到目标 13下标为 62.2 每一行代码背后的理由很多教程会把代码贴出来就完事了但我觉得不解释清楚为什么这么写你看完还是一头雾水换个场景照样写错。所以我逐段说明第一初始边界为什么是len(data)-1因为这是闭区间的写法right 指向的是真实存在于切片中的最后一个元素。如果data是空的len(data)-1等于 -1此时left 0left right不成立循环直接跳过函数返回 -1。这个细节其实已经帮我们处理了空切片的情况。第二mid : left (right-left)1为什么不用(leftright)/2这是经典的整型溢出问题。如果 left 和 right 都是很大的整数leftright可能超出 int 类型的表示范围。虽然 Go 的 int 在不同平台位数不同64 位平台上溢出概率很低但防御式编程没有坏处。right-left不会溢出右移一位等价于除以 2而且位运算的速度在某些热路径上会更快。第三比较判断的顺序问题。我习惯先判断data[mid] target因为这是能找到目标时最直接的分支如果不等再根据大小关系缩小范围。注意两个分支的边界更新必须是mid1和mid-1而不是mid。如果写成left mid或者right mid就可能导致死循环——比如当 left right 时mid 还是等于 left更新后范围不变循环永远跳不出来。第四循环结束后为什么直接返回 -1当left right时说明区间为空整个有序切片已经被我们翻遍了找不到目标。这里其实有个隐藏信息——此时left指向的位置就是 target 应该插入的位置这个性质在查找插入位置的变体题里非常有用后面我会专门讲。2.3 一次完整的查找过程演示为了让你对代码执行过程有直观认知我用data : []int{1, 3, 5, 7, 9, 11, 13, 15, 17, 19}和target : 13来手动走一遍循环。轮次leftrightmiddata[mid]比较结果下一次边界109499 13目标在右left 525971515 13目标在左right 635651111 13目标在右left 646661313 13命中返回下标 6四轮比较从上到下最多 10 个元素对数时间复杂度 O(log n) 的优势在这一刻体现得很明显。如果线性扫描最坏要比较 10 次当数据量到百万级时线性扫描可能要百万次二分查找最多 20 次差距就是这么大。3. 边界条件与死循环最容易翻车的几个场景3.1 目标不存在的返回判断先看一个很经典的问题如果 target 不存在于数组中left最终会停在哪里代码运行时如果target小于最小元素那么每一次 mid 位置的数都比 target 大right 不断左移最终right会变成 -1left停在 0。如果target大于最大元素则 left 不断右移最终left变成len(data)right 停在len(data)-1。如果 target 的值落在数组范围内但不存在left 会停在一个比 target 大一点的元素位置这恰好就是如果要插入 target它应该插入的位置。这个行为在 LeetCode 的搜索插入位置题目里就是标准答案。所以我们的BinarySearch函数虽然返回 -1 表示没找到但调用方如果还想知道插入位置可以通过看 left 来获取前提是你把返回值改成left而非 -1或者额外返回一个布尔值。3.2 目标在边界时的正确性验证很多人写二分查找时最怕的就是 target 正好是第一个元素或者最后一个元素。我用上面的代码分析一下如果 target 等于 data[0]第一轮 mid 大概率大于 0data[mid] targetright 不断左移最终当left 0, right 0时mid 等于 0命中并返回 0。如果 target 等于 data[len(data)-1]同理left 不断右移最终命中最后一个下标。边界情形只要你的区间更新规则正确就一定不会漏掉。反而那些在循环末尾写return -1的代码如果循环条件或更新规则错误才会出现 target 明明在数组中却返回 -1 的诡异现象。3.3 死循环到底是怎么产生的死循环是二分查找最让人头疼的问题。我们来构造一个必死的场景分析它的成因假设你写了半开区间版本[left, right)但是循环条件错误地写成left right同时当nums[mid] target时错误地把 left 更新为 mid 而不是 mid1。手动推演一个数组[1, 3, 5]target 是 5。初始 left0, right3。mid1data[1]3 5left 更新为 1本应更新为 2。下一轮 left1, right3mid2data[2]5 5命中返回这里碰巧没死循环。但如果 target 是 6 呢mid2data[2]5 6left 更新为 2。下一轮 left2, right3mid2data[2]5 6left 又更新为 2。此时 left 永远等于 2right 永远等于 3循环永不退出。这就是著名的left mid导致的死循环问题。要避免它最稳妥的办法只有两个要么遵循我们前面说的闭区间规则排除 mid 时更新为mid1或mid-1要么在半开区间版本中left mid1和right mid严格配套。只要更新规则里出现了left mid而循环条件又是left right绝大多数情况下会死在某些特殊输入上。3.4 空数组和单元素数组的边界测试写代码必须考虑极端输入。我列一个表格演示我们的标准实现在不同长度的切片上表现如何输入切片target预期结果实际行为[]5-1left0right-1循环不执行返回 -1[5]50left0right0mid0命中返回 0[5]3-1mid0data[0]5 3right-1循环退出[3, 5]51第一轮 mid03 5left1第二轮命中给我再多几个特殊输入实际上都不必担心——只要你的循环条件、边界更新规则正确这些极端场景全部在控制范围内。我平时的测试策略是先在测试代码里写这些极端 case之后再随机数组测试后者后面有专门章节讲。4. 从查一个数到查边界标准库 sort.Search 与二分查找变体4.1 Go 标准库 sort.Search 怎么用Go 的sort包内置了Search函数它本质上就是二分查找但语义不是查找等于某个值的下标而是查找第一个满足条件 f(i) 为 true 的下标。函数签名如下func Search(n int, f func(int) bool) int它的行为是在[0, n)范围内找到最小的下标 i使得f(i)为 true。前提是f必须呈现从 false 到 true 的单调性也就是说对于所有小于目标下标的元素返回 false大于等于目标下标的元素返回 true。如果用来在有序切片 data 中查找 target 是否存在我可以这样写package main import ( fmt sort ) func main() { data : []int{1, 3, 5, 7, 9, 11, 13, 15} target : 7 // sort.Search 返回第一个满足 data[i] target 的下标 idx : sort.Search(len(data), func(i int) bool { return data[i] target }) if idx len(data) data[idx] target { fmt.Printf(找到目标 %d下标为 %d\n, target, idx) } else { fmt.Printf(未找到目标 %d插入位置为 %d\n, target, idx) } }注意sort.Search内部的二分查找区间是半开区间[0, n)而不是闭区间。所以它返回的 idx 可能等于 n表示所有元素都小于 target。4.2 查找左边界第一个等于 target 的位置现实业务里经常会遇到数组中有重复元素我要找第一个等于 target 的下标这类问题。上面的标准BinarySearch返回的可能是任意一个匹配位置不一定是第一个。怎么改核心思路是当data[mid] target时我们不要急着返回而是把 right 移到 mid-1继续在左半部分找因为左边可能还有等于 target 的元素。最终循环结束时left 就是第一个等于 target 的位置。// SearchFirstEqual 返回第一个等于 target 的下标如果不存在则返回 -1 func SearchFirstEqual(data []int, target int) int { left, right : 0, len(data)-1 first : -1 for left right { mid : left (right-left)1 if data[mid] target { // 当前元素大于等于 target如果等于则记录当前位置 if data[mid] target { first mid } right mid - 1 } else { left mid 1 } } return first }这个变体利用了单调性思想找到任何一个匹配位置后继续向左压缩查找范围直到把范围耗尽。最终记录下来的 last 命中位置就是最左侧的匹配。同理如果要把条件改成data[mid] target找到的就是第一个大于 target 的下标这在业务里可能对应找上边界。有基础的读者应该已经发现这些变体都可以用sort.Search配合不同的比较函数实现其实殊途同归。4.3 手动实现与标准库的对比有些人盲目迷信标准库也有人觉得标准库难懂坚持手写。我的看法是标准库代码经过了无数人的 review 和测试正确性和鲁棒性远超普通开发者随手写出的版本但手写二分查找的思维训练是标准库无法替代的。面试时被要求手写考察的就是你对区间不变量、边界更新的理解深度背答案没意义。对比维度手写 BinarySearchsort.Search灵活性需要自己控制每种变体通过闭包条件灵活调整可读性代码直观易教学回调函数稍显抽象性能无额外函数调用开销有闭包调用开销但编译器通常能内联出错风险边界条件写错容易翻车官方实现正确性有保障实际工程里如果只是简单查一个有序切片里是否存在某值我会直接用sort.Search或者sort.SearchInts后者更省事但本质上是一回事。如果我要实现一个复杂的数据结构内部逻辑比如跳表、区间树之类我会手写二分并严格控制区间规则。4.4 使用 sort.SearchInts 的快速路径如果你的数据就是[]int其实最方便的是sort.SearchInts(data, target)它等价于Search(len(data), func(i int) bool { return data[i] target })。代码会清爽很多idx : sort.SearchInts(data, target) if idx len(data) data[idx] target { // 找到 } else { // 未找到idx 是插入位置 }这个写法在 LeetCode 刷题和日常开发里都很推荐简单不易错。5. 二分查找在真实项目中的落地场景5.1 有序配置里的快速定位我在做后端服务时经常遇到这样的场景系统里维护了一个根据用户等级查对应权限配置的有序列表等级越高权限越大。这个列表是排好序的每次请求都要查一次用户等级对应的权限配置是什么。数据量不大但请求量非常大如果用线性扫描虽然也不慢但总给人一种浪费的感觉。换成二分查找后代码性能更稳定而且逻辑上更清晰地表达了等级有序这个前提。类似场景还有IP 归属地查询。IP 地址可以转换成整数然后在一个排序好的 IP 区间段里二分查找对应的省份城市。这种区间匹配本质上也可以借助二分查找的变体来完成——先二分找到最接近的起点再判断是否落在某个区间内。5.2 数值逼近求平方根、求对数等二分查找不止能查数组下标还可以用于数值逼近。比如在实现某些数学函数时要求一个数的平方根且不允许使用系统库常见的做法就是用二分法逼近设定左边界 0右边界为 x不断取中间值看它的平方是否接近 x直到误差小于阈值。这种写法的优势在于思路简单、数值稳定缺点是收敛速度不如牛顿迭代法快。但在嵌入式或者要求确定性的系统里二分逼近因为行为可预期反而更受欢迎。我上学时用 C 写过类似的函数后来用 Go 重构代码结构基本不变// Sqrt 使用二分法计算 x 的平方根precision 为允许误差 func Sqrt(x float64, precision float64) float64 { if x 0 { return -1 // 或返回错误 } if x 0 || x 1 { return x } low, high : 0.0, x if x 1 { // 小于 1 的数平方根反而比原数大 high 1 } for high-low precision { mid : (low high) / 2 if mid*mid x { high mid } else { low mid } } return (low high) / 2 }注意这里x 1时把 high 设为 1否则 0.25 的平方根 0.5 根本不在查找区间内这是数值逼近题里容易忽略的一个小坑。5.3 时间序列与日志索引的搜索时序数据库或者日志系统里数据通常按时间戳排序查询某个时间段内的数据时可以先二分定位起始时间戳再顺序遍历直到超出结束时间。尤其当日志量极大、不可能全量扫描时二分查找就是第一道筛子。举个例子某个文件里按行存储了带时间戳的日志每行开头是时间戳。我先通过二分找到第一个时间戳大于等于 startTime的行号再从该行往后读到时间戳超过 endTime 为止。这样哪怕文件有几千万行一次查询的定位操作也只有几十次比较。5.4 高频面试题的通用解法面试题里二分查找的变体简直太多了旋转数组找最小值、旋转数组找目标值、二维矩阵查找、寻找峰值等等本质上都是在有序或部分有序的空间里利用折半排除思想。以寻找峰值为例题目要求在一个数组中找一个元素它比左右邻居都大数组中相邻元素不相等。如果直接线性扫描很简单但进阶要求 O(log n)。这时候二分思想就派上用场了取中点 mid如果 nums[mid] nums[mid1]说明峰值在左侧或就是 midright mid否则说明上坡出现在右侧left mid1。这个题不需要数组整体有序只靠局部单调性就能二分算是二分查找思想的高级应用。理解了区间不变量和单调性这类变体题比背题解有用得多。6. 我在实战中踩过的坑和推荐的测试方法6.1 一次真实的生产教训我之前在做一个规则引擎里面有一个有序的费率表用户不同的消费金额对应不同的费率。当时我想当然地手写了一个二分查找把循环条件写成了left right然后边界更新规则里有一个分支写成了left mid。结果上线后发现某些金额区间会计算出不存在的费率导致用户账单异常。排查了很久才定位到是二分查找死循环和边界错误导致的。那次事故之后我做了一个决定凡是排序切片里的查询一律优先使用sort.Search除非有非常特殊的性能要求否则不手写二分。手写二分只保留在刷题、学习以及确实需要自定义复杂逻辑的场景里。6.2 用随机数组对拍验证正确性无论你手写代码时多么自信也一定要用测试来验证。我推荐对拍测试用官方库或暴力线性查找作为参照随机生成大量测试数据比较手写二分和线性查找的结果是否一致。package main import ( math/rand sort testing ) func TestBinarySearchRandom(t *testing.T) { for n : 0; n 1000; n { // 生成一个长度随机的有序切片 size : rand.Intn(100) data : make([]int, size) for i : range data { data[i] rand.Intn(100) } sort.Ints(data) target : rand.Intn(120) - 10 // 允许出现一些不在范围内的值 got : BinarySearch(data, target) // 线性扫描参照 want : -1 for i, v : range data { if v target { want i break } } if got ! want { t.Fatalf(data%v target%d got%d want%d, data, target, got, want) } } }这段测试代码我建议直接放进你的项目里跑一跑。随机数组能覆盖大多数边界组合比如重复元素、目标在最左最右、目标不存在等。6.3 使用 go test 做覆盖测试Go 自带go test工具配合上面的测试函数名TestBinarySearchRandom你只需要在终端里运行go test -v -count1-count1的意思是禁用测试缓存确保每次都重新运行。如果你的代码实现了BinarySearch和SearchFirstEqual可以在同一个测试文件里多写几个测试函数形成一套稳定的回归测试集。6.4 关于整数溢出的额外补充虽然 Go 的 int 在 64 位平台上几乎不可能因为leftright溢出但如果你在做算法题时用了类似 C 的语言int 固定 32 位或者数据规模达到 10^9 级别溢出问题就真实存在。养成写mid : left (right-left)1的习惯是成本极低的防御。这一点在任何编程语言里都适用属于通用的好习惯。7. 最后一个值得记住的小技巧我在实际编码中还有一个很常用的习惯当二分查找的变体比较复杂时先写出sort.Search版本的代码确认逻辑正确后再按需改写成手写版本。因为sort.Search的语义非常明确——找第一个使条件成立的下标基于它推演边界条件比基于裸的二分查找容易得多。如果哪天你发现自己陷入了二分查找的死循环或边界错误不要急着盲改代码。退一步在纸上画出 left、right、mid 的变化轨迹问自己三个问题我现在用的是闭区间还是半开区间循环不变式是否始终成立当 mid 不满足条件时left 或 right 是否严格缩小了范围大多数错误都逃不过这灵魂三问。二分查找的代码可能只有十几行但它考验的是对不变量和边界条件的深刻理解。能把这十几行写对、写稳、在需要时还能变出花来你的编程基本功就已经超过很多人了。希望这篇内容对你有所帮助也欢迎你把你自己踩过的二分查找的坑分享在评论区咱们互相取取经。