工作几年之后我发现自己写业务代码越来越顺手但一碰到需要“绕弯”的问题就开始卡壳。有时候明明知道该用哪个数据结构却说不清为什么刷题看题解能看懂关上答案自己写却总是差一步。于是我做了一个决定——开一个“每日算法练习”系列每天至少拿出完整的一两个小时把经典算法从原理到实现重新过一遍。这是Day01也是这个系列的第一篇。今天的练习组合是二分查找、归并排序和贪心找零。这三道题分别对应了三个最基础的能力边界条件的把控、分治思想的手感、以及贪心策略的证明意识。文章会把我实际的练习过程、代码和踩坑点都写出来。如果你也正打算重新捡起算法或者刚入门想找一个可参考的练习节奏这篇应该能给你一些可复现的思路。1. 首日题单选型为什么从“能跑通的经典题”开始很多人一开始就挑战动态规划、KMP、红黑树这类硬核问题结果往往是看了三天题解代码还是抄不顺畅最后放弃。我的建议很朴素第一天甚至前两周都别碰那些“看一眼就觉得自己不会”的题先把基础能力磨扎实。今天选的三道题难度都不高但每个都值得反复练二分查找算法代码只有短短几行可它考察的是循环不变量、区间定义、溢出处理。能把这个边界焊死的人写其他算法也不容易埋雷。归并排序算法最容易理解的O(n log n)排序含分治、递归、合并三个动作。理解了它后面学快排、堆排会轻松非常多。贪心算法思路直白但最怕“局部最优不等于全局最优”的反例。用找零问题正好可以在“对与错”之间做对比。这三题串起来正好覆盖了“查找、排序、策略”三个维度。第一天的目标不是“AC多少题”而是“把每一题的为什么讲清楚”。我做题的时候给自己定了个规矩代码跑通不算完必须能答上来三个问题——为什么这样写是对的、边界在哪里、换个数据还会不会出问题。实际写下来我发现这个要求比想象中难得多。二分查找写了两个版本归并排序调了五分钟的递归边界贪心找零在一组特殊面额上翻了车。这正好说明“简单题”背后并不简单。如果你也准备开启自己的每日算法练习我建议第一天不要贪多把两到三个经典题吃透比快进快出看十道题有用。2. 二分查找第一天就把边界条件焊死2.1 从标准写法到“为什么不能写错”二分查找的代码网上随便一搜就是一堆但真正自己默写一遍才明白边界条件有多容易出错。我今天的第一个练习是在有序数组中查找目标值存在则返回下标不存在则返回-1。先看我一开始写的版本#include vector int binarySearch(std::vectorint nums, int target) { int left 0; int right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { return mid; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return -1; }这个版本应该是大家最熟悉的。但如果你把循环条件换成while (left right)或者把left mid 1写成left mid后面就可能出现一系列问题要么漏掉目标值要么死循环。拿一个具体的测试来演示。[1, 3, 5, 7, 9]里找7left0right4mid2nums[2]5小于7所以left变成了3。下一轮left3right4mid3nums[3]7刚好命中。一切正常。但如果改成while (left right)当left和right相邻时比如left3right4mid3发现nums[3]7直接返回了这里看起来也正常。可一旦目标值不是7而是9while (left right)状态下最后left会停留到下标4循环结束返回-1就错了。所以我的建议是第一版的标准闭区间写法循环条件固定用left rightmid更新用left (right - left) / 2。这样区间始终是闭区间[left, right]逻辑最直白不容易自我混淆。2.2 mid计算的溢出陷阱这里要单独说一个老生常谈但值得刻进肌肉记忆的问题——mid溢出。如果直接写(left right) / 2当数组足够大、left和right都接近int上限时leftright会溢出成负数mid就错了。用left (right - left) / 2本质上是先算区间长度的一半再从左边界出发。这个写法在数学上等价于(left right) / 2但避开了加法溢出。我在本机上用一个理论上的大数组模拟过旧写法确实会出现mid为负的情况而新写法一切正常。2.3 进阶练习找第一个等于target的位置跑通基础版之后我又练了一个更贴近实战的变体找第一个等于target的下标。这个场景在二分答案、区间查询里经常遇到。实现方式是把“找到target立即返回”改成“找到了继续向左收缩”int findFirst(std::vectorint nums, int target) { int left 0; int right nums.size() - 1; int result -1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { result mid; right mid - 1; } else if (nums[mid] target) { left mid 1; } else { right mid - 1; } } return result; }用[1, 3, 3, 3, 5, 7]测这个函数目标是返回下标1而不是2或3。中间过程会有多次收缩最终落在最左侧的3上。这个变体比基础版更能检验你是否真的理解区间变化建议第一次练习就一并写掉。2.4 二分查找的适用前提二分查找的前提是“单调性”数组本身必须有序。不过很多新手不知道单调性不一定表现为数组已经完全排好序。比如“找到第一个满足某个条件的值”只要判断条件在数组下标上呈现true/false的单调变化就能套二分。这个思路在后续的“二分答案”类型题里会非常常用。今天我在笔记里记了一句话二分查找的核心不是“查找”而是不断维护一个有效的候选区间。每轮迭代你都要保证target如果在数组里就一定还在[left, right]这个区间内。只要这个区间定义不变代码就不会乱。把这句话记住基本就掌握了二分查找的精髓。3. 排序算法里的手感练习归并排序与快排的选择3.1 为什么第一道排序题选归并排序算法有很多冒泡、选择、插入、归并、快速、堆排……今天我没有选最常考的快速排序而是选了归并排序。原因很简单归并排序的代码结构最规整分治思想最容易讲清楚也没有像快排那样恼人的partition边界问题。归并排序的整个过程是先把数组从中间劈开分别排序左右两半再把两个有序序列合并成一个。这个“先分后治”的过程非常直观代码也几乎不需要什么技巧只要递归边界和合并逻辑别写错。3.2 默写一遍归并排序下面是我今天实际默写的实现#include vector void mergeSort(std::vectorint nums, int left, int right) { if (left right) { return; } int mid left (right - left) / 2; mergeSort(nums, left, mid); mergeSort(nums, mid 1, right); std::vectorint tmp(right - left 1); int i left; int j mid 1; int k 0; while (i mid j right) { if (nums[i] nums[j]) { tmp[k] nums[i]; } else { tmp[k] nums[j]; } } while (i mid) { tmp[k] nums[i]; } while (j right) { tmp[k] nums[j]; } for (int p 0; p (int)tmp.size(); p) { nums[left p] tmp[p]; } }写完之后要特别注意两个点。第一递归的终止条件left right不能漏少了它就会出现死递归然后栈溢出。第二合并过程中如果nums[i] nums[j]我选择把左边数组的元素先放进去这样归并排序是稳定的。稳定的含义是相等元素的相对顺序在排序前后不变。在某些场景下这一点很重要比如按多个关键字排序时先按主关键字排再按次关键字排稳定的算法能保留之前的排序结果。3.3 用测试数据验证自己的理解我拿这组数据实际跑了一下[38, 27, 43, 3, 9, 82, 10]。手动追踪一遍过程第一次切分left0, right6, mid3分成[38, 27, 43, 3]和[9, 82, 10]。左侧继续切直到每个区间只剩一个元素。从最小单元开始合并比如[38]和[27]合并成[27, 38][43]和[3]合并成[3, 43]再合并成[3, 27, 38, 43]。右侧同理最终合并成[3, 9, 10, 27, 38, 43, 82]。跑下来结果正确时我特意又加了几个测试空数组、只有一个元素的数组、全相等数组。空数组调用mergeSort(nums, 0, nums.size() - 1)由于left0right-1直接触发left right返回不崩溃。这个情况很多初写者会忽略我自己第一遍也漏了后来用if (nums.size() 1)包了一层才安心。3.4 归并排序的时间复杂度直觉O(n log n)这个结论不能只是背。我用今天的代码想了一下每一轮合并所有元素都会被扫描一遍一共要切分log n层。每一层扫描合并都是O(n)所以总复杂度是O(n log n)。空间复杂度方面每层递归会创建临时数组但合并结束后临时数组会被释放所以峰值空间是O(n)。这也是它相比冒泡排序、插入排序的最大优势数据规模一大O(n²)直接扛不住。当然归并排序也有弱点它不是原地排序需要额外内存而且常数因子比快速排序大。正因为各有优劣工程上才有混合排序的策略。我今天的练习目的不是选出“最好的排序算法”而是通过代码建立对分治的直觉后面学快排时再对比就轻松多了。4. 贪心算法第一课用找零问题建立策略意识4.1 先写一版“直觉代码”贪心算法的核心思想是每一步都做当前看起来最优的选择希望最终能达成全局最优。找零问题是最经典的入门例子假设你有面额为[1, 5, 10, 25]的硬币要凑出某个金额如何用最少的硬币数。我第一版代码很直接def min_coins_greedy(coins, amount): coins.sort(reverseTrue) count 0 for coin in coins: if amount 0: break count amount // coin amount % coin return count if amount 0 else -1 print(min_coins_greedy([1, 5, 10, 25], 36))这个写法就是尽可能先用大面额硬币。36美分的话先拿一个25剩11再拿一个10剩1再拿一个1总共3枚。手动验证确实是3枚硬币看起来没问题。4.2 换一组硬币面额反例马上出现如果以为贪心在所有场景下都成立那就大错特错了。我把硬币面额换成[1, 3, 4]要凑6贪心会怎么做取一个4剩2取两个1总共3枚。可最优解呢取两个3只需要2枚。贪心在这里失效了。这个反例让我反思贪心不是“无脑逼近”它需要满足特定的结构比如“大面额是小面额的整数倍”这种特殊关系。在[1, 5, 10, 25]这套面额下10是5的倍数25是5的倍数所以大面额的替换永远不亏。但在[1, 3, 4]里4和3之间没有整除关系拿4可能堵死后续的组合反而得不偿失。网上很多讲贪心算法的题解只强调“每步选最优”很少强调反例验证。我在第一天的笔记里专门写了一段写贪心算法题先问自己两个问题——这个局部最优能不能带到下一步如果存在多个局部最优选哪个才能保证不会破坏全局最优。回答不上来就去试试构造反例。4.3 对比动态规划才是“兜底方案”既然贪心不是万能的那找零问题的通用解法是什么答案是动态规划。用dp[i]表示凑出金额i所需的最少硬币数递推公式是dp[i] min(dp[i - coin] 1)遍历所有coin面额且coin i。我把这个递推也写了一遍def min_coins_dp(coins, amount): dp [float(inf)] * (amount 1) dp[0] 0 for i in range(1, amount 1): for coin in coins: if i coin: dp[i] min(dp[i], dp[i - coin] 1) return dp[amount] if dp[amount] ! float(inf) else -1 print(min_coins_dp([1, 3, 4], 6))输出是2。对着刚才贪心输出的3差距一目了然。但我第一天并不打算把动态规划铺开只是用这个例子告诉自己贪心的策略意识很重要可也要知道它的适用边界。后面系列学到动态规划时这个天花板和反例会重新出现。4.4 做这题真正的收获很多解法教程会直接告诉你“这题贪心能过”然后就完事了。但如果你只是记住了这个结论换个面额体系就会踩坑。我今天用这个例子反复练习的是如何从“直觉”走向“论证”在[1, 5, 10, 25]下为什么贪心一定对核心是面额之间的倍数关系保证了“替换不会变差”。后续做更复杂的贪心题我会习惯性做三件事写直觉解法、构造反例、再想证明思路。即便反例构造不出来我也会因为多做了这个环节而对自己的答案更有信心。5. 首日的坑与复盘三个让我卡住的小问题今天题目本身不算难但实际写起来还是遇到了一些“意料之中”和“意料之外”的问题。我把其中三个典型的记录下来都是新手容易撞上的。5.1 坑一二分查找里left (right - left) / 2看起来啰嗦但确实是防线我一开始图省事写成了int mid (left right) / 2;。在小数组上一切正常但我用一个模拟大边界的测试去跑时发现mid可能变成负值。原因就是left和right相加后超过了int上限。这个问题在真实项目中不常见但在算法题里一旦出现就是那种“偶尔卡死、很难复现”的隐秘bug。所以二分查找的mid计算我以后一律写left (right - left) / 2。这不是炫技是防身。5.2 坑二归并排序的递归边界写错直接栈溢出写归并排序时我第一版把终止条件写成了if (left right) return;。看起来也没什么问题但一旦传入的数组为空left0right-1这时left ! right递归就会继续算mid往一个不存在的区间递归最终爆栈。改成if (left right) return;之后空数组、单元素数组都能安全退出。别小看这个它把非法区间的场景一并覆盖了。写递归函数的时候最好养成用而不是做终止条件的习惯尤其是区间型递归。5.3 坑三贪心找零的反例让我意识到“能跑通”不等于“算法对”如果只做[1, 5, 10, 25]那组数据贪心找零看起来就是完美的。可当我换到[1, 3, 4]找6时贪心给出了3枚而不是最优的2枚。这个反例不是靠调试调出来的是刻意构造出来的。它给我的启示是验证算法不能只依赖一两个测试用例。特别是贪心、DP这类策略型算法最好有几组“刁钻”的手工样例——包括重复元素、边界值、特殊矛盾的数据。如果能构造出一个让直觉挂掉的反例那对这个算法的理解反而会上一个台阶。5.4 排错心法把“算法正确”和“实现正确”分开检查今天我排错时有个小技巧先不急着看代码逻辑而是先确认算法思路本身对不对再确认实现细节。二分查找边界错了可能是思路里的区间定义不明确归并排序爆栈可能是递归终止条件的问题贪心不对可能是策略本身就不适用于这组数据。把这两类问题分开能少走很多弯路。比如我在归并排序里发现结果不对时我先在纸上画出切分和合并过程确定思路正确才去逐行查循环里的下标。这种做法强烈推荐给同样在练习算法的朋友。6. 明天练什么聊聊这个系列怎么持续下去Day01只是开始如果想靠一天的热情把算法吃透基本不现实。我给自己定的规则是每天必须留下可追踪的记录哪怕只是写几行笔记、跑几个测试用例。有了Day01的基础我在计划Day02的安排。目前的想法是这样的日期练习主题目标Day01二分查找、归并排序、贪心找零理解区间维护、分治合并、贪心边界Day02快速排序与partition细节对比归并排序理解原地排序的代价Day03链表基础与双指针技巧熟悉快慢指针复盘环检测Day04单调栈与滑动窗口学会用数据结构维护候选集合Day05经典动态规划入门从斐波那契到背包雏形Day06本周题单回顾与手写总结重新默写检验是否真的掌握排序方面快速排序的partition边界是出了名的容易写错而且面试常考链表双指针则和Day01的二分查找一样都是“代码量少但细节多”的题型。把这两类安排在系列的前几天能把基础打得更扎实。另外我打算在每天结束时做一次“默写检验”不打开任何资料把当天的核心算法写到能跑通为止。今天我已经用这个方式检验了二分查找和归并排序效果很好因为这能强行逼自己找出记忆里模糊的部分。你在做每日算法练习时也可以试试这个办法它比“看着题解点头”有效得多。最后再分享一个小习惯把每道题的错误样例保留下来放进一个专门的文件里。我今天的[1, 3, 4]找零反例就属于这种保留样例以后复习时可以快速唤醒记忆也能提醒自己不要踩同一个坑第二次。希望这个系列能像今天的Day01一样扎扎实实走下去。