教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本篇基于「算法通关手册」仓库中的 0278. 第一个错误的版本 题解文档完整讲解如何利用版本状态的单调性将找第一个坏版本转化为二分查找问题并把仓库中二分查找专题文档的边界细节区间开闭、mid 取值、循环条件、排除法落到这道交互题上。读完你可以独立写出正确且不陷入死循环的二分边界代码并迁移到二分答案类题目。题目概览标签数组、二分查找、交互难度简单题目来源力扣 0278 First Bad Version仓库中收录于 docs/solutions/0200-0299/分类清单见 docs/00_preface/00_06_categories_list.md 的二分查找题目一节题目大意描述给你一个整数 $n$代表已经发布的版本号同时给你一个用于检测版本是否出错的接口isBadVersion(version):。要求找出第一次出错的版本号 $bad$。说明要求尽可能减少对isBadVersion(version):接口的调用次数数据范围$1 \le bad \le n \le 2^{31} - 1$。示例示例 1输入n 5, bad 4 输出4 解释 调用 isBadVersion(3) - false 调用 isBadVersion(5) - true 调用 isBadVersion(4) - true 所以4 是第一个错误的版本。示例 2输入n 1, bad 1 输出1核心洞察错误版本状态天然单调这道题虽然给的是接口调用但背后隐藏着一个关键性质如果版本v是好版本isBadVersion(v) false那么v之前的所有版本也一定是好版本如果版本v是坏版本isBadVersion(v) true那么v之后的所有版本也一定是坏版本。换句话说把版本号 $1 \sim n$ 依次检测返回序列一定是若干个false后跟着若干个true只会发生一次从好到坏的翻转。bad正是这个翻转点——它是第一个返回true的版本。这一性质与仓库二分查找专题文档 docs/01_array/01_13_array_binary_search_01.md 中强调的减而治之思想完全吻合二分查找每一步都排除掉一定不包含目标的区间只在可能包含目标的区间内继续。这里的目标不再是某个相等的值而是一个布尔谓词第一次变为真的位置。既然检测结果是单调的我们就可以在 $[1, n]$ 上做二分每次调用isBadVersion(mid)只需一次接口调用就能确定bad在左半边还是右半边最终在 $O(\log n)$ 次调用内收敛。解题思路二分查找排除法思路推导设左右指针left 1、right n维护闭区间 $[left, right]$循环条件为left right。每次取中点mid并调用接口isBadVersion(mid)返回true说明mid及之后的版本都是坏版本而我们要找的是第一个坏版本所以mid有可能是答案不能把它排除只能排除(mid, right]令right midisBadVersion(mid)返回false说明mid及之前的版本都是好版本bad一定在mid之后可以放心排除[left, mid]令left mid 1。循环终止时必然有left right此时区间收缩到只剩一个元素这个位置就是第一个坏版本。参考代码class Solution: def firstBadVersion(self, n): left 1 right n while left right: mid (left right) // 2 if isBadVersion(mid): right mid else: left mid 1 return left逐步推演以 n 5, bad 4 为例轮次leftrightmidisBadVersion(mid)操作1153falseleft 42454trueright 4344——循环结束返回 4整个流程只调用了 2 次isBadVersion就定位到了坏版本 4与题目示例给出的isBadVersion(3) - false、isBadVersion(4) - true的调用序列一致。对比最坏情况下线性扫描需要调用 $n$ 次接口二分查找的调用次数是 $\log_2 n$ 级别这正是题目尽可能减少接口调用要求的落点。复杂度分析时间复杂度$O(\log n)$。每轮循环区间减半二分查找的时间复杂度为 $O(\log n)$即接口调用次数为 $O(\log n)$。空间复杂度$O(1)$。只使用了left、right、mid三个常数空间变量。二分查找边界细节这道题为什么这么写很多初学者能写出常规二分却总在边界问题上犯错。仓库专题文档 docs/01_array/01_14_array_binary_search_02.md 系统总结了二分查找的四大细节区间开闭、mid 取值、循环条件、区间收缩方式。这里结合本题逐一对照1. 区间开闭左闭右闭初始化left 1、right n两个端点都是有效版本属于左闭右闭区间 $[left, right]$。专题文档明确推荐统一使用左闭右闭写法边界逻辑更简单、更不易出错。2. mid 取值向下取整 防溢出写法代码中mid (left right) // 2是向下取整。由于 Python 的整数不会溢出直接相加即可但若在 C/C/Java 等语言中left right可能溢出专题文档推荐等价写法mid left (right - left) // 2本题的收缩方式是left mid 1与right mid配对这种组合必须搭配向下取整的 mid详见下文第 4 点。3. 循环条件left right本题采用left right而不是left right。原因是每次循环都会排除一部分确定不含答案的区间left mid 1或right mid区间必然严格缩小循环结束时left right区间只剩一个候选元素它必然是第一个坏版本直接返回left即可无需像直接法那样在循环内判断相等或额外判断nums[left]。4. 为什么 right mid 而不是 right mid - 1这是本题与查找目标值类二分最核心的区别在 0704. 二分查找 这类直接法题目中nums[mid] target时说明目标在左侧且mid不是目标所以right mid - 1在本题中isBadVersion(mid) true只能说明mid是坏版本但不能排除mid就是第一个坏版本。因此必须保留mid令right mid。这正是专题文档中排除法的核心每次只排除目标元素一定不存在的区间mid可能包含答案时绝不排除。5. 死循环防范left mid 才需要向上取整专题文档给出了一条重要记忆规则只要出现left mid就必须让 mid向上取整mid left (right - left 1) // 2否则当区间只剩两个元素时left mid会导致区间无法收缩、陷入死循环。本题的分支是left mid 1和right mid不存在left mid因此使用向下取整的mid (left right) // 2是安全且正确的——这是本题写法与 0034. 在排序数组中查找元素的第一个和最后一个位置 中第二次二分找右边界写法的关键区别后者需要left mid因而必须向上取整。仓库中的配套学习路径本题在仓库中有完整的学习闭环建议按以下顺序深入算法基础篇二分查找算法介绍与简单实现讲解算法步骤、减而治之思想、直接法代码细节进阶篇二分查找细节详解区间开闭、mid 取值、循环条件、直接法 vs 排除法、死循环防范同类交互题0374. 猜数字大小——同样通过接口交互做二分但返回值是 -1/0/1 三态适合对比记忆边界查找题0035. 搜索插入位置找第一个不小于 target 的位置、0034. 在排序数组中查找元素的第一个和最后一个位置左右边界两次排除法题目清单二分查找分类题目见 docs/00_preface/00_06_categories_list.md章节索引见 docs/solutions/0200-0299/index.md。此外仓库在 codes/python/ 目录按 01_array、02_linked_list、03_stack_queue_hash_table 等模块配套实现了大量数据结构与排序算法源码可与题解文档对照阅读巩固对数组、链表等底层结构的理解。扩展思考从查找值到二分答案本题是**二分答案单调谓词二分**这一大类问题的入门模板只要问题的判断函数谓词关于参数单调本题为版本状态从 false 单调翻转为 true就可以把在有序数组中找一个值的二分思想迁移到在答案空间里找边界。仓库分类清单中标注的进阶题正是同一思路的应用0875. 爱吃香蕉的珂珂在吃香蕉速度上二分谓词是能否在 H 小时内吃完1011. 在 D 天内送达包裹的能力在运载能力上二分谓词是能否在 D 天内运完。这类题目与本题的写法高度一致mid满足条件时收敛右边界保留 mid不满足时收缩左边界left mid 1最终left即为答案。总结0278. 第一个错误的版本 是一道把交互接口与二分查找结合的经典简单题要点可以浓缩为识别单调性好版本在前、坏版本在后目标是从 false 翻转到 true 的第一个位置用排除法二分isBadVersion(mid) true时right midmid 可能是答案false时left mid 1mid 一定不是答案循环条件用left right配合向下取整的mid left (right - left) // 2终止时left right直接返回复杂度为 $O(\log n)$ 时间、$O(1)$ 空间接口调用次数随版本总数对数增长。掌握本题也就掌握了二分答案类问题最核心的写法骨架。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐First Bad Version 题解用二分查找在 O(log n) 内定位首个错误版本First Bad Version 题解用二分查找在 O log n 内定位首个错误版本 导读 本文基于 LeetCode 经典问题 278. First B示例工程教程LeetCode-Book 题解精读第一个错误的版本278——用二分查找定位首个故障版本LeetCode Book 题解精读第一个错误的版本278——用二分查找定位首个故障版本 导读 《278. 第一个错误的版本》是 LeetCode 二分查示例工程LeetCode-Go 题解 278First Bad Version第一个错误的版本二分查找实战LeetCode Go 题解 278First Bad Version第一个错误的版本二分查找实战 导读 本文基于 LeetCode Go https:/示例工程上一篇AtlasOS显卡性能优化指南三步拿回被后台吃掉的GPU性能下一篇VCRUNTIME140.dll 报错不再怕Visual C 运行库一键安装包实测分享创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考