二分查找在排序数组查找元素2——这个标题一看就是算法课或者PTA题库里的题目但我跟你说能把二分查找一次写对的人真的比想象中少。标题后面带个(2)我猜要么是你第二次碰这道题要么是题库里的第二版总之透着一股我之前交过一回在哪儿翻的车的味道。这篇文章不打算泛泛讲概念而是把二分查找彻底掰开它凭什么比遍历快边界为什么那么容易错PTA的函数题到底在考你什么以及那些找第一个/找最后一个的变体到底怎么套模板。无论你是刚学到二分查找的初学者还是在反复提交被WA折磨的备考人这篇应该能帮你一次弄透。1. 为什么写出来的二分查找总差一点先弄明白它到底在干什么1.1 从挨个找到跳着找二分查找省时间的真相二分查找的本质一句话就能说清在有序序列里每次把目标值和中间元素比较直接排除掉一半数据然后只在剩下那一半里继续找。它的高效来源于每次比较都传递了大量信息——你不仅知道了中间元素和目标的大小关系还顺带知道了中间元素之前或之后的所有元素和目标元素的关系因为数组是有序的。对比一下就明白了。假设有一本一千页的书你要找第528页。顺序查找的做法是从第1页开始翻一页一页往后找最坏情况要翻1000页。二分查找的做法是直接翻到第500页发现目标页在它后面那就把前面500页全丢掉再翻到第750页发现目标页在它前面丢掉后面250页……这样每次翻一次剩下的范围缩小一半最多翻10次左右就到了。这个差距用数字说话更直观。一个包含1亿个元素的有序数组顺序查找最多需要比较1亿次二分查找需要多少次log2(1e8)大约是27次。1亿次和27次这就是二分查找存在的意义。而在PTA和很多面试题的测试数据里数组长度动辄10^5甚至10^6如果题目明确要求时间复杂度O(logn)你不写二分等着你的就是超时。很多人背下了二分查找的模板但写出的代码总是看起来对却过不了全部测试点。原因几乎都出在同一个地方边界条件的语义没有想清楚。这不是记不记得住代码的问题而是你没搞明白你的区间到底是什么。1.2 有序性为什么是铁律乱序数组二分会发生什么二分查找的适用前提是排序数组这个前提必须死记。为什么会这样因为二分查找每一次排除一半数据的依据是如果中间元素小于目标值且数组升序那么中间元素左边的所有元素都小于等于中间元素必然也都小于目标值所以左边一整片都可以扔掉。这一步推断完全依赖数组有序这个性质。如果数组无序中间元素和目标值的比较结果对你判断目标值在左边还是右边没有任何帮助。举个极端例子数组是[5, 1, 4, 2, 3]目标值是2。第一次取中间元素4,4比2大按二分逻辑应该去左边找,但2恰好在右边。你不仅没排除一半反而直接把正确答案排除掉了后续全是瞎找。所以在无序数组上执行二分查找结果是不确定的可能找不到目标可能找到错误的位置。标题里特意写明在排序数组查找元素就是在告诉你这个算法的前提条件已经给你了你要做的就是在有序的前提下把查找过程做对。但题目给的前提有时是个坑——比如PTA那道经典题就写的是递减有序数组方向反了你背的升序模板直接失效这个我后面详细说。2. 手写一个能跑对的二分查找四种边界写法逐个拆2.1 循环条件用 还是 左右边界怎么收缩写二分查找第一件事是确定你用的是哪种区间模型。最常见的两种是左闭右闭和左闭右开。这俩表面看只是循环条件差一个等号实际上决定了下标怎么更新。先看最经典、最容易理解的左闭右闭写法int binary_search(int arr[], int n, int target) { int left 0, right n - 1; // 区间 [left, right]左右都能取到 while (left right) { // 区间不为空left right 时还有一个元素要检查 int mid left (right - left) / 2; if (arr[mid] target) { return mid; } else if (arr[mid] target) { left mid 1; // mid 已经检查过往右找就排除它 } else { right mid - 1; // mid 已经检查过往左找就排除它 } } return -1; // 没找到 }这里的关键点是既然区间是[left, right]left right时区间里还有一个元素所以循环条件必须是否则这个元素永远不检查。而收缩时因为mid已经在这次循环里比较过了无论往左还是往右都应该排除mid本身也就是left mid 1或right mid - 1。再看左闭右开写法int binary_search_left_open(int arr[], int n, int target) { int left 0, right n; // 区间 [left, right)right 本身不可取 while (left right) { // left right 时区间为空 int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; // 排除 mid同时保留左闭语义 } else { right mid; // mid 可能是答案保留它 } } return left; // 返回第一个 target 的位置 }左闭右开的作用通常是找第一个满足条件的位置。这里right n是因为n这个下标不在数组内但它可以作为区间的终点哨兵。while (left right)意味着left right时区间已空。当arr[mid] target时mid可能就是我们要找的位置不能排除它所以让right mid而不是mid - 1。两种写法的对照关系模型初始区间循环条件mid 偏大时mid 偏小时循环结束时 left/right 语义左闭右闭[0, n-1]left rightright mid - 1left mid 1区间为空left 是第一个大于 target 的位置左闭右开[0, n)left rightright midleft mid 1left right是第一个 target 的位置我个人的建议是初学者先把左闭右闭这一种写到滚瓜烂熟它最符合直觉也最容易手动验证。等你把边界彻底理解了再去看左闭右开的变体会从容得多。最忌讳的是今天写左闭右闭明天写左闭右开把两种模型的边界更新规则混着用——right mid和right mid - 1差一个位置混用的结果就是死循环或者漏查。2.2 mid 计算的坑加法溢出和死循环是怎么产生的mid的计算方式看起来是个小问题其实藏着两个值得说的坑。第一个坑(left right) / 2可能溢出。当left和right都是很大的整数时比如left 1500000000、right 1800000000两者相加约等于33亿超出了32位int能表示的最大值21亿左右结果会变成一个负数再除以2mid就完全错了。正确写法是left (right - left) / 2先算差值再除以2差值最多是数组长度不会溢出。这个细节在C语言面试和PTA的大数据测试点里都能派上用场。第二个坑区间不收缩导致的死循环。很多人的二分查找不是死在找不到而是死在永远在循环。来看这个错误写法while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid; // 错误应为 mid 1 } else { right mid; // 在左闭右闭下这也错应为 mid - 1 } }假设left 0, right 1那么mid 0。如果arr[0] target执行left mid此时left还是0right还是1下一次循环mid还是0再下一次还是0——死循环了因为left根本没往前挪。同理right mid在区间长度缩小到2时也可能让right停在原地。规则就一条在左闭右闭模型下每次循环mid必然被排除绝不允许把mid重新赋给left或right。这类死循环最隐蔽的情况是区间长度为2。如果你在调试时发现程序卡住先看left和right是不是在循环里一个不变、另一个也不变如果是九成是收缩写错了。3. PTA函数题里的二分查找判题机到底想让你交什么3.1 List结构、下标语义和返回值约定PTA上那道经典的二分查找函数题很多人第一次提交都是信心满满WA成一片。原因很简单函数题不是让你实现一个通用算法而是让你严格按照题面定义的接口、数据结构和返回值约定来完成。你算法写得再对接口语义错了就是0分。我以这道题典型的题面为例Position BinarySearch( List L, ElementType X );题面会给出这样的结构体定义typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; // 线性表中最后一个元素的位置 };注意读题时的几个关键信息点几乎每一个都是坑Data数组从下标1开始存储还是从0开始PTA这道题通常明确写了元素从下标1开始存储所以查找区间不是[0, Last]而是[1, Last]而且返回的下标也是从1开始计的。数组是递增有序还是递减有序我记得这道经典题给的是递减有序。也就是说Data[1]最大Data[Last]最小。你用升序模板去写整个逻辑全反。找不到时返回什么题面一般要求返回一个NotFound这个NotFound通常是#define NotFound 0。因为有效下标从1开始所以0才可以作为不存在的标记。如果你习惯性地返回-1那这两个测试点必然错。返回类型是Position不是ElementType。有人写到最后直接return X;类型都对不上编译可能能过但逻辑必然错。针对这个题面下标1开始、递减有序、失败返回NotFound0一个合格的函数实现长这样#define NotFound 0 Position BinarySearch( List L, ElementType X ) { Position left 1, right L-Last; while (left right) { Position mid left (right - left) / 2; if (L-Data[mid] X) { return mid; } else if (L-Data[mid] X) { left mid 1; // 递减有序中间值比X大说明X在右侧 } else { right mid - 1; // 中间值比X小说明X在左侧 } } return NotFound; }这里比较方向是反着来的因为数组递减Data[mid] X时目标值在更右边更小的元素方向所以收缩左边反之收缩右边。如果套用升序模板不仅找不到还会在极少数情况下碰上死循环。3.2 我见过的五种边界提交错误和修复对比我在给人看代码的时候发现错误其实就集中在那几个点。下面这几种情况覆盖了大多数WA的原因错误行为错误后果正确修复初始区间写成 [0, Last]多查了一个无效下标0如果返回0会和NotFound混淆确认题面存储起点从1开始就写left1用升序的比较方向递减数组下必错先判断题面是递增还是递减再定收缩方向while (left right)区间还剩最后一个元素时直接退出左闭右闭用或改成左闭右开模型right mid 而不是 mid - 1区间长度剩2时死循环左闭右闭下 strict 排除 mid找不到返回 -1题面要求NotFound0答案错误返回题面定义的特殊标记除了这些还有一类隐蔽问题是测试点设计判题数据通常会专门测目标在数组两端目标在中间目标不存在且介于两个元素之间数组只有一个元素数组长度很大导致mid溢出这些情况。所以函数题提交前不要只测{1, 2, 3, 4, 5}找3这种理想用例至少把边界用例在脑子里过一遍。4. 二分的变体并不难查找第一个/最后一个的通用模板4.1 找第一个大于等于目标值的位置下界现实中很多时候你并不需要找到等于目标值的那个下标而是要找到第一个可以放进去的位置。最常见的需求就是lower_bound在有序数组里返回第一个 target 的元素下标。这个用左闭右开模型写起来非常顺int lower_bound(int arr[], int n, int target) { int left 0, right n; // 区间 [left, right) while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; // 排除所有小于 target 的元素 } else { right mid; // arr[mid] targetmid 可能是答案保留 } } return left; // 第一个 target 的下标 }为什么要用左闭右开而不是左闭右闭因为right mid这种写法能保留候选位置不会因为mid - 1把可能的答案排除掉。如果用左闭右闭还得额外用一个变量记答案写起来绕。举个例子arr [1, 3, 3, 5, 7, 9]target 3。lower_bound应返回1因为下标1是最早出现3的地方。手动跑一遍left0,right6,mid3arr[3]53所以right3mid(03)/21arr[1]33right1mid(01)/20arr[0]13left1此时leftright返回1。这个方法在统计有序数组中某个值的出现次数时特别有用upper_bound(arr, target) - lower_bound(arr, target)就是重复次数。比如统计[1, 3, 3, 3, 5]中3的个数lower_bound返回1upper_bound第一个3的位置返回44-13。4.2 找最后一个小于等于目标值的位置上界在4.1的基础上改一个符号就得到上界。找最后一个 target 的元素下标标准写法int upper_bound(int arr[], int n, int target) { int left 0, right n; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) { left mid 1; // 这个位置也可能满足条件继续往后找 } else { right mid; // 第一个 target 的位置 } } return left - 1; // 前一个就是最后一个 target 的位置 }注意这个函数返回的是left - 1。因为循环结束后left指向的是第一个大于target的位置它减1就是最后一个小于等于target的位置。用这个模板可以解决一类经典题在单调函数上求零点位置。比如求sqrt(x)的整数部分不用数学库可以看成在[0, x]范围内找最后一个满足mid * mid x的midint my_sqrt(int x) { int left 0, right x 1; // 区间 [0, x1) while (left right) { int mid left (right - left) / 2; if ((long long)mid * mid x) { left mid 1; } else { right mid; } } return left - 1; }这个写法其实就是在套上界模板找最后一个平方不大于x的数。注意mid * mid可能超出int范围所以转成long long再比较这个细节很容易被忽略但对大测试点很关键。4.3 二分答案的思路从查找位置到查找值还有一种二分应用叫二分答案思路和在排序数组查找元素有相通之处但对象不同。二分答案不是在一个现成的有序数组里找目标值而是在一个单调的取值范围内二分搜索问题的答案。典型的例子是木材切割问题给定几根原木长度要求切成至少k段等长的小段问最长能切多长。答案一定在[1, max_len]区间内且区间是单调的答案越大能切的段数越少。于是可以每次枚举mid计算当前mid能切多少段如果段数够就说明mid可以更大继续向右二分否则说明mid太大了向左二分。这种题和普通二分查找的代码框架一模一样区别只是比较arr[mid]和target变成了计算check(mid)的结果是否满足条件。很多看似和二分查找无关的题目本质上都是在答案值域上做二分这些经验可以特别留意。5. 二分查找实战题目过了不算稳这些经验帮我少踩坑5.1 提交前必做的几个极端用例自查写完代码别急着交先在心里或本地跑这样一组数据数组中只有一个元素查找它、查找比它大的、查找比它小的。只有1个元素的时候最容易暴露循环条件写错、区间初始化错的问题。目标值在数组最左端和最右端验证收缩方向是否正确。目标值不存在但落在数组最大和最小之间比如数组[1, 4, 6]查5正常应该返回应该插入的位置或NotFound但如果有边界错误可能死循环或返回错误位置。数组长度为2这是死循环的高发区。[1, 2]查3、查0、查2分别跑一遍基本能验证区间收缩是否真的在缩短。数组量级极大用100000个元素验证left (right - left) / 2不会溢出。C语言的(left right)/2在left和right接近2^31时必炸。我自己的习惯是不管多简单的二分模板提交前都先拿一个长度为2、一个长度为3的用例手工推一遍整个过程不超过两分钟却能挡掉七八成WA。因为边界错误往往就在这些极短数组上暴露。5.2 二分查找思路能移植到的真实场景二分查找不只是考试题工程里它的应用非常广。举几个我现在还能想到的例子有序数据的精确查找比如在有序ID列表里判断某个ID是否存在一次查询从O(n)变成O(logn)。区间定位根据IP地址的起始区间有序表查找某个IP属于哪个地域本质上是在一个区间数组里做二分查找。这跟在排序数组查找元素的思路完全一致只是每个元素是一个区间。单调函数求值求方程的近似根、求满足条件的最小/最大值都是二分答案的变体。版本回溯与二分定位在有序的历史版本号或时间戳中定位某个事件发生的边界位置也是二分查找。这些场景有一个共同点只要你能在一个有序序列上定义一个判定规则并且判定结果满足单调性就能用二分查找或二分答案去解决。这也是为什么这个算法虽然代码简单却被认为是必须熟练掌握的基本功。它考的不只是你会不会写循环而是你能不能把一个实际问题抽象成一个可以在单调空间里搜索的问题。5.3 我的个人习惯一套写法用到底再加一个断言最后说一点写二分的个人习惯。我会始终统一使用左闭右闭模型来对付查找等于目标值的场景用左闭右开模型来对付查找边界位置的场景绝不混用。每次写完后我会刻意检查收缩代码里是否有left mid或right mid出现在左闭右闭模型中——一旦出现基本等于死循环。然后我会在代码里加一个可选的断言仅调试用// 调试断言示例 // assert(0 left right n);这句断言看起来没用但在排查越界时很有效。比如right不小心写成n1或者某次收缩让left越过right断言能第一时间在本地炸出来而不是等到线上数据才暴雷。如果你现在正被某个二分查找的边界问题困扰听我的把区间模型和收缩规则写在注释里找个长度为2的数组跑一遍大概率立刻就能看出自己哪里写拧了。很多时候不是你不会二分而是你把自己绕进了记模板但不记语义的坑里把边界想清楚这题就真通了。