企业官网建设流程全解析

训练营第一天：二分查找，你真的会写吗？

其实二分查找是很多人在算法刷题路上的第一道坎，也可能是第一道“自以为会写，一写就错”的题。很多同学看到“有序数组、查找目标值”第一反应是for循环扫一遍，这当然不算错，但当你真正面对海量数据、超时限制、或者面试官追问“你能优化到 O(log n) 吗”的时候，暴力解法就不够用了。代码随想录算法训练营第一天安排二分查找，我觉得选得非常妙——它足够简单，能让你快速找到刷题的手感；又足够经典，能让你在细节里体会“算法不是背模板，而是理解边界”这句话。

今天这篇文章我会围绕二分查找的适用范围、三种常见写法、边界条件、实战题目和我自己踩过的坑来展开。不管你是刚接触算法的 C 语言初学者，还是在用 C++、Java、Python 刷题的同学，这篇文章都能给你一些参考。

1. 二分查找解决什么问题：从线性扫描到折半搜索

1.1 二分搜索的基本思想：每一次都“砍一半”

二分查找的核心思想非常简单：在一个有序序列中查找目标值，每次都把搜索区间缩小一半。相当于你在一本按拼音排序的通讯录里找“张三”，正常人不会从第一页翻到最后一页，而是会从中间翻开，根据“张”的拼音位置决定往前翻还是往后翻，然后不断缩小范围。这个习惯性的动作，就是二分查找。

在算法层面上，二分查找每次比较中间元素与目标值，根据比较结果把搜索区间缩小一半，直到找到目标值或者区间为空为止。关键在于这个“区间”到底是什么——左闭右闭[left, right]还是左闭右开[left, right)——这会直接影响循环条件和边界的更新方式。很多同学死循环或者结果不对，根源往往不是二分思想没理解，而是“区间定义”没想清楚。

1.2 适用范围：有序、可随机访问、单调性

二分查找并不是万能的，它有几个前置条件：

• 数据必须有序。这是前提。如果数组无序，二分查找的结果就不可靠，除非你先排序，但排序本身已经至少是 O(n log n) 了。
• 支持随机访问。数组可以，链表不行。因为二分查找需要快速定位中间元素，链表只能顺序访问，即使链表有序，二分查找的时间复杂度也会退化到 O(n)。
• 存在单调性。如果是查找“某个满足条件的最值”这类问题，只要答案具备单调性，也可以尝试用二分思想来逼近答案，比如查找第一个大于等于目标值的位置、旋转数组中的最小值等，这类题本质上是“二分答案”。

说白了，二分查找的核心价值就是：把 O(n) 的查找降到 O(log n)，在数据量大的时候，这个优势是指数级的。比如 10 亿条数据，线性查找最坏要 10 亿次比较，而二分查找最多 30 次就能定位到目标值。

2. 三种常见写法：左闭右闭、左闭右开、左开右开

2.1 写法一：左闭右闭[left, right]

这是我认为最适合入门、也最容易理解的写法。定义left = 0，right = nums.length - 1，每次搜索区间包含left和right两个端点，所以循环条件是while (left <= right)，因为当left == right时，区间内还有一个元素需要检查。

int binarySearch(vector<int>& 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; }

注意这里有两个细节：第一，mid用left + (right - left) / 2而不是(left + right) / 2，原因是left + right可能超出int范围导致溢出，虽然一般情况下不会发生，但这是一个好习惯。第二，当nums[mid] < target时，说明目标值在右半边，因为mid已经检查过不是目标值，所以新的区间左端应该是mid + 1；同理，目标值在左半边时，新的区间右端是mid - 1。这是和“左闭右闭”这个定义严格配套的，不能随意修改。

2.2 写法二：左闭右开[left, right)

这种写法在 C++ 的标准库中被广泛使用，比如vector的迭代器区间就是左闭右开。right指向的是搜索区间之外的位置，所以循环条件是while (left < right)，因为当left == right时，区间已经空了。

int binarySearch(vector<int>& nums, int target) { int left = 0; int right = nums.size(); // 左闭右开 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; // 保持右开 } return -1; }

这种写法中，right的更新是right = mid而不是mid - 1，原因很简单：区间是左闭右开的，mid本身不在新的搜索区间内，但mid这个位置不包含在右边界里，所以把right更新为mid就相当于把区间缩小到了[left, mid)。如果把right更新为mid - 1，就会漏掉mid - 1这个位置，这属于边界错误，新手很容易犯。

2.3 为什么推荐统一用左闭右闭

我在训练营里给同学们的建议是：平时刷题，统一用左闭右闭的写法就好。原因有两个：

第一，左闭右闭的区间定义和人类的直觉更接近，left和right都被包含在搜索范围内，循环条件left <= right配合left = mid + 1、right = mid - 1的更新方式，逻辑闭环清晰，不容易写乱。

第二，当你后续接触更复杂的问题时，比如“查找第一个大于等于 target 的位置”这类变体，左闭右闭的思路更容易迁移。你只要记住“区间包含 left 和 right”这个前提，边界条件就不会乱。

当然，左闭右开也有它的优势，尤其是配合 C++ 的迭代器思想，以及处理一些“区间分割”问题时，天然避免right变成负数。但作为入门，先搞定一种写法，再触类旁通，我会建议从左闭右闭开始。

3. 初版代码的多个实现：C 语言、C++、Python 版本对比

3.1 C 语言实现

C 语言没有vector这些容器，数组长度需要自己传参。写法上和一维数组的指针操作别无二致，关键是不要越界。

int search(int* nums, int numsSize, int target) { int left = 0; int right = numsSize - 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; }

C 语言版本需要注意几个问题：第一，numsSize如果是0，说明数组为空，应该直接返回 -1。上面的代码中left = 0，right = -1，循环条件left <= right不成立，自动返回 -1，所以其实是安全的。第二，如果你在刷题平台上看到 PTA 或者 SDUT 的实验题，往往要求你实现binarySearch函数，入参就是这种 C 风格，所以这个模板要记牢。

3.2 C++ 实现

C++ 实现和上面写的模板一致，可以直接用vector，代码更简洁，也更接近刷题平台的输入输出方式。

class Solution { public: int search(vector<int>& 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; } };

这里额外说一个 C++ 里的常见坑：nums.size()返回的是size_t类型，是无符号整数。如果你直接int right = nums.size() - 1;当nums为空时，nums.size()是0，0 - 1的结果是size_t类型下的超大值，再赋给int后是-1，这个没问题。但如果你把left、right都声明为int后和nums.size()混算，可能出现类型转换警告甚至意外结果，建议统一用int显式转换，或者用(int)nums.size()。

3.3 Python 实现

Python 的代码最简洁，但也要注意整数溢出问题在 Python 里不存在，不过mid的计算方式我建议还是保留left + (right - left) // 2的写法，和 C++ 保持逻辑一致。

def search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1

Python 有一个便利是切片nums[mid:]可以直接做递归，但我不建议你这么写——切片会创建新数组，时间复杂度和空间复杂度都变成 O(n)，二分查找的 O(log n) 优势就没了。

4. 常见变体：搜索插入位置、查找左边界、查找右边界

4.1 搜索插入位置（LeetCode 35）

这道题是二分查找的经典变体：给定一个排序数组和一个目标值，如果找到目标值就返回下标，找不到则返回它按顺序插入的位置。本质上是在查找“第一个大于等于 target 的元素位置”。

int searchInsert(vector<int>& nums, int target) { int left = 0; int right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else right = mid; } return left; }

这里我用了左闭右开写法，是因为这个问题的语义天然适合“返回第一个满足条件的位置”。right初始化为nums.size()，如果目标值比所有元素都大，那插入位置就是数组末尾，left会遍历到nums.size()，正好是答案。这个版本的代码不需要在循环里判断nums[mid] == target，因为查找结束后left就是第一个大于等于 target 的位置，如果找到了 target，它也是 target 的下标。

4.2 查找左边界和右边界（LeetCode 34）

这道题要求你在一个可能包含重复元素的排序数组中找到目标值的第一个和最后一个位置。很多同学会想：先二分找到任意一个 target，然后向左右线性扩展找边界。这在数据量小的时候没问题，但最坏情况下（比如数组全是相同的数）会退化成 O(n)，这就失去了二分的意义。

正确的做法是用两次二分：一次查找左边界，一次查找右边界。

vector<int> searchRange(vector<int>& nums, int target) { int left = 0, right = nums.size(); vector<int> res = {-1, -1}; // 查找左边界 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else right = mid; } if (left == nums.size() || nums[left] != target) return res; res[0] = left; // 查找右边界 left = 0; right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) left = mid + 1; else right = mid; } res[1] = left - 1; return res; }

查找左边界的关键在于：nums[mid] == target时，不着急返回，而是把right收缩到mid，继续往左边找。查找右边界则反过来：nums[mid] <= target时，把left移到mid + 1，这样循环结束后left指向的是第一个大于 target 的位置，减一就是右边界。

4.3 旋转排序数组的最小值（LeetCode 153）

还有一个高频变形题是查找旋转有序数组中的最小值。比如数组[4,5,6,7,0,1,2]，原本是升序的，在某一点旋转了。这个问题的关键是：将nums[mid]与nums[right]比较，如果nums[mid] > nums[right]，说明最小值在右半部分；否则在左半部分。这个思路也是很多大厂面试的常客，训练营后几天我也会专门讲这类“二分答案”的题目。

5. 常见错误与排查技巧：死循环、越界和溢出

5.1 死循环是怎么来的

二分查找里死循环不是因为你笨，而是因为边界更新和循环条件不匹配。最常见的死循环组合是：while (left <= right)+left = mid或者right = mid。当left + right恰好是偶数时，mid等于left，如果此时nums[mid] < target，left = mid之后 left 没有变化，下次循环mid还是同样的值，进入死循环。

解决办法其实很简单：如果循环条件是left <= right，那么边界更新必须保证区间严格缩小，所以要么left = mid + 1，要么right = mid - 1。只有在while (left < right)时，left = mid + 1或right = mid才是安全的。一句话总结：循环条件的等号和边界更新的加减一是配套的，不能乱配。

5.2 越界问题

越界通常发生在两个地方。第一个是left或right超出数组范围。比如在查找右边界时，left - 1可能变成 -1，在访问nums[left - 1]之前一定要先判断left是否大于 0。第二个是mid计算时的溢出，前面已经说过，用left + (right - left) / 2可以完美规避。

5.3 刷题平台上的特殊坑

在 C 语言刷题平台（比如 PTA、SDUT 的实验）上，函数题往往会给你一个不完整的函数签名，比如没有传入数组长度，或者要求你在全局数组中操作。遇到这种题目，先把题目给的所有参数用上，再考虑边界。常见的一个坑是数组下标从 1 开始而不是 0，比如某些题目描述的线性表位置从 1 计数，此时二分查找的初始边界应该是left = 1、right = n，返回的下标也是从 1 开始的，不要惯性思维一上来就从 0 开始。

5.4 调试二分查找的实用技巧

我个人的习惯是，遇到二分查找出问题，直接用几个典型用例手动模拟一遍：

• 空数组：[]
• 只有一个元素：[5]，查找 5 和查找 3
• 两个元素：[1, 3]，查找 1、2、3
• 多个相同元素：[1, 2, 2, 2, 3]，查找 2

手动模拟时，把每一步的left、right、mid、nums[mid]写出来，基本上一两分钟就能定位到问题。这是最笨但最有效的方法，比盯着代码看半小时都管用。

6. 从第一天开始的刷题方法论：如何构建自己的算法模板

6.1 算法模板：不要背，要理解后内化

代码随想录强调“模板化”学习，但我不建议机械地背诵模板。你要做的是理解每一种模板背后对应的“区间定义”，这样即使题目变化，你依然能灵活修改边界条件。

我自己的实践方法是：给每种模板写一个注释版，把区间定义、循环条件、边界更新方式都写在代码里。比如左闭右闭：

// [left, right] 区间查找 // 循环条件 left <= right，因为 left == right 时区间内仍有一个元素 // left = mid + 1: target 在右侧，mid 已排除 // right = mid - 1: target 在左侧，mid 已排除

这样当你做变体题时，改起来很清楚：要查找左边界，就把nums[mid] == target时的行为从return mid改成right = mid，同时把循环条件改成left < right。

6.2 第一天的题目清单怎么练

训练营第一天的题目通常包括：

• LeetCode 704 二分查找（裸二分，闭眼默写）
• LeetCode 35 搜索插入位置（变体：返回第一个大于等于 target 的位置）
• LeetCode 34 在排序数组中查找元素的第一个和最后一个位置（左右边界）
• LeetCode 69 x 的平方根（二分答案思想的入门题）

这些题目的难度是递进的，我建议按顺序刷。704 是为了建立肌肉记忆，35 开始让你思考边界，34 则让你必须理解“为什么相等时要收缩右边界”。69 题则是跳出数组，在答案域上做二分，眼界一下子就打开了。

6.3 复盘远比刷题数量重要

训练营第一天结束后，不要着急刷更多的题，先花半小时复盘今天写的每一道题。问自己三个问题：这道题的核心矛盾是什么？我用的是哪个模板？如果我改用另一种区间定义，代码会变成什么样？

复盘的核心是“输出”，你可以在纸上画出每一步 left、right 的变化过程，也可以把你理解的二分查找讲给同学听——能给别人讲明白，才是真的掌握了。

7. 我的个人练习习惯：三天后重新做一遍

我在训练营里带过很多同学，发现一个普遍现象：第一天学二分查找，当时懂了，过三天再做，又写错了。这不是因为你记忆力差，而是因为“当时懂”是短时记忆，还没有沉淀成长期记忆。

所以我有一条非常实用的建议：三天后，把今天的题目重新刷一遍，不参考任何资料。如果还能一遍 AC，说明真的掌握了；如果卡住了，恭喜你，这正是查漏补缺的好机会。二刷时的调试过程会比一刷时更有价值，因为你会在熟悉的地方再次犯错，而这个错误恰恰暴露了你的理解漏洞。

另外，我强烈建议大家把二分查找的代码模板整理到自己的笔记里，用注释写清楚每个细节。我当时整理的时候，光是“循环条件”和“边界更新”这两个点就反复修改了五六次才确定下自己最舒服的版本。这套笔记后来帮了我大忙，每次遇到二分变体题，我只需要在自己的模板上做少量修改，就能快速写出正确的代码。

从第一天开始，就养成“总结模板、反复刷错题、讲给别人听”的习惯，这比每天刷十道新题更有价值。等你坚持训练两周、一个月后回头看，会发现今天这些边界问题都成了肌肉记忆，再也不需要刻意去想了。