从猜数字游戏到算法面试C二分查找的两种区间写法深度解析想象一下和朋友玩猜数字游戏对方心里想着1到100之间的一个数字你每次猜测后他会告诉你大了或小了直到猜中为止。聪明的玩家不会随机乱猜而是采用一种系统性的方法——每次选择当前范围的中间值根据反馈缩小搜索范围。这种策略正是计算机科学中二分查找算法的核心思想。在编程面试中二分查找是必考的基础算法之一。看似简单但很多候选人在实现时常常陷入边界条件的泥潭。究其原因是对搜索区间的定义理解不够透彻。本文将从一个生活化的猜数字场景出发逐步深入分析二分查找的两种经典区间写法——左闭右闭[ ]和左闭右开[ )通过图示、代码对比和逐步演算帮你彻底掌握这一重要算法。1. 二分查找基础从直觉到形式化二分查找(Binary Search)是一种在有序集合中高效查找特定元素的算法。它的时间复杂度是O(log n)比线性查找的O(n)高效得多。让我们先用猜数字的例子建立直观理解假设要在1-100中猜数字57最优的猜测序列会是猜50中间值→ 小了新的范围51-100猜75 → 大了范围51-74猜62 → 大了范围51-61猜56 → 小了范围57-61猜59 → 大了范围57-58猜57 → 命中这个过程中每次猜测都将搜索范围缩小一半。将其形式化为算法需要考虑三个关键要素搜索区间当前查找的范围边界终止条件何时停止查找区间更新如何根据比较结果调整边界在编程实现中区间的表示方式直接影响代码的写法。最常见的两种是左闭右闭区间[left, right]包含左右边界左闭右开区间[left, right)包含左边界但不含右边界2. 左闭右闭区间写法详解左闭右闭区间表示法是最直观的一种方式即搜索范围包含左右两个边界。让我们用C代码实现并分析每个细节。2.1 基本实现int binarySearch(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) { right mid - 1; // 调整右边界 } else if (nums[mid] target) { left mid 1; // 调整左边界 } else { return mid; // 找到目标 } } return -1; // 未找到 }2.2 关键点解析初始边界设置right nums.size() - 1因为要包含最后一个元素循环条件left right当left right时区间[left, right]仍然包含一个元素需要继续检查中间值计算mid left (right - left) / 2比(leftright)/2更安全避免整数溢出边界更新找到mid后因为mid已经检查过所以新区间应排除midnums[mid] target目标在左半区更新right mid - 1nums[mid] target目标在右半区更新left mid 12.3 示例演算假设在有序数组[1,3,5,7,9]中查找5循环次数leftrightmidnums[mid]动作10425等于目标返回2查找4的过程循环次数leftrightmidnums[mid]动作10425大于4right120101小于4left131113小于4left2421--退出循环未找到3. 左闭右开区间写法详解左闭右开区间是另一种常见的表示方法右边界不包含在搜索范围内。这种写法在某些情况下更为简洁。3.1 基本实现int binarySearch(vectorint nums, int target) { int left 0; int right nums.size(); // 初始右边界不包含 while (left right) { // 注意没有等号 int mid left (right - left) / 2; if (nums[mid] target) { right mid; // 调整右边界 } else if (nums[mid] target) { left mid 1; } else { return mid; } } return -1; }3.2 关键点解析初始边界设置right nums.size()因为右边界不包含循环条件left right当left right时区间[left, right)为空停止查找边界更新nums[mid] target因为右边界不包含所以right mid不需要-1nums[mid] target左边界包含所以仍要left mid 13.3 示例演算同样在[1,3,5,7,9]中查找5循环次数leftrightmidnums[mid]动作10525等于目标返回2查找4的过程循环次数leftrightmidnums[mid]动作10525大于4right220213小于4left2322--退出循环未找到4. 两种写法的对比与选择4.1 关键差异总结特性左闭右闭[ ]左闭右开[ )初始right值nums.size() - 1nums.size()循环条件left rightleft rightright更新right mid - 1right mid区间含义包含左右边界包含左边界不包含右边界空区间表示left rightleft right4.2 如何选择两种写法都是正确的选择取决于个人偏好和具体场景左闭右闭的优势更直观区间定义与数学表示一致适合处理包含明确左右边界的场景左闭右开的优势右边界更新更简单不需要-1与C STL的迭代器范围约定一致end()指向末尾后一位在某些边界条件下代码更简洁提示建议初学者先掌握一种写法推荐左闭右闭彻底理解后再学习另一种。面试时可以向面试官说明你使用的区间定义。4.3 常见错误与调试技巧即使理解了原理实现时仍容易犯以下错误无限循环检查循环条件和边界更新是否匹配确保每次迭代区间都在缩小漏掉元素检查终止条件是否过早结束确保边界更新没有跳过潜在解整数溢出使用mid left (right - left) / 2而非(left right) / 2调试时可以打印每次循环的left、right、mid值在小数组上手动演算测试边界情况如查找第一个/最后一个元素5. 二分查找的变体与应用掌握了基本写法后可以进一步学习二分查找的变体它们在面试中也经常出现5.1 查找第一个/最后一个匹配项当数组有重复元素时可能需要找到目标值的第一个或最后一个出现位置。// 查找第一个等于target的位置 int firstEqual(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid - 1; } else { left mid 1; } } return (left nums.size() nums[left] target) ? left : -1; }5.2 查找插入位置LeetCode 35题要求返回目标值应插入的位置使数组仍保持有序。int searchInsert(vectorint nums, int target) { int left 0, right nums.size(); // 使用左闭右开 while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid; } else { left mid 1; } } return left; }5.3 旋转排序数组中的搜索在部分有序的旋转数组中搜索如LeetCode 33题需要额外判断哪一部分是有序的。int search(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) return mid; if (nums[left] nums[mid]) { // 左半部分有序 if (nums[left] target target nums[mid]) { right mid - 1; } else { left mid 1; } } else { // 右半部分有序 if (nums[mid] target target nums[right]) { left mid 1; } else { right mid - 1; } } } return -1; }6. 面试实战建议在算法面试中二分查找题目非常常见。以下是一些实战建议明确前提条件确认数组是否有序是否有重复元素是否需要返回特定位置第一个/最后一个选择区间表示法向面试官说明你使用的区间定义保持代码与区间定义一致测试边界情况空数组单元素数组目标值不存在目标值是第一个/最后一个元素复杂度分析时间复杂度O(log n)空间复杂度O(1)迭代实现常见题目基础二分查找LeetCode 704搜索插入位置35在排序数组中查找元素的第一个和最后一个位置34搜索旋转排序数组33寻找峰值162在实际面试中我曾遇到过一位候选人他能够清晰地解释两种区间写法的区别并通过画图展示搜索范围的变化最终给出了无懈可击的实现。这种对基础算法的深刻理解往往能给面试官留下深刻印象。