二分查找：不只是查一个数那么简单
二分查找，说白了就是在一个有序数组里快速找到目标值。每次砍掉一半，时间复杂度 O(log n)。听起来简单？嗯，但我在面试中见过太多人栽在边界条件上。
我个人习惯把二分查找分成三个层次：标准模板、变种问题、高级应用。今天咱们就把这三个层次彻底讲透。
一、标准二分查找模板
先看最基础的版本——在有序数组中查找一个数，存在返回索引，不存在返回 -1。
int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 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;
}
💡 我的习惯：用
left + (right - left) / 2 而不是 (left + right) / 2。为什么？防止 left + right 溢出。虽然现在很多语言不会溢出，但这是个好习惯。
这里有个关键点：while (left <= right) 用的是 <=。为什么不是 <？你想想看，当 left == right 时，当前元素还没检查过，必须再进一次循环。
二、变种问题：寻找左右边界
实际项目中，我们经常遇到「找第一个大于等于 target 的位置」或「找最后一个小于等于 target 的位置」。这就是二分查找的变种——寻找左右边界。
举个例子：[1, 2, 2, 2, 3, 4]，target = 2。
- 左边界：第一个 2 的位置 → 索引 1
- 右边界：最后一个 2 的位置 → 索引 3
寻找左边界（第一个 >= target）
int leftBound(int[] nums, int target) {
int left = 0, right = nums.length; // 注意 right 开区间
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid; // 收缩右边界
} else {
left = mid + 1;
}
}
return left; // left 就是第一个 >= target 的位置
}
⚠️ 我曾经踩过的坑：一开始我总把 right 初始化为 nums.length - 1，结果边界情况总是出错。后来我改用「左闭右开」区间（right = nums.length），代码一下子清爽了。记住：左闭右开是处理边界问题的利器。
寻找右边界（最后一个 <= target）
int rightBound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1; // 收缩左边界
} else {
right = mid;
}
}
return left - 1; // left - 1 就是最后一个 <= target 的位置
}
注意看，右边界返回的是 left - 1。为什么？因为循环结束时 left 指向的是第一个大于 target 的位置，所以 left - 1 就是最后一个等于 target 的位置。
三、经典例题：搜索旋转排序数组
这是 LeetCode 第 33 题，也是我面试时最喜欢问的一道题。题目是这样的：
一个原本有序的数组在某个未知点发生了旋转，比如 [0,1,2,4,5,6,7] 变成了 [4,5,6,7,0,1,2]。给你一个 target，要求 O(log n) 时间找到它。
核心思路：虽然整体不是有序的，但每次二分后，至少有一半是有序的。
int search(int[] nums, int target) {
int left = 0, right = nums.length - 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;
}
🎯 关键点：判断有序区间时，用
nums[left] <= nums[mid] 而不是 nums[left] < nums[mid]。为什么？因为当 left == mid 时（比如数组只有两个元素），必须用 <= 才能正确进入左半有序的分支。
四、知识体系总览
下面这张图总结了二分查找的核心知识结构，我建议你把它记在脑子里：
五、避坑指南与实战经验
我在项目中用过很多次二分查找，总结出几个容易踩的坑：
- 死循环：当 left 和 right 相邻时，如果 mid 计算方式不对，可能永远跳不出循环。我建议统一用
mid = left + (right - left) / 2，向下取整。 - 边界漏判：比如数组只有一个元素时，你的代码能正确处理吗？我曾经就因为这个 bug 被测试同学追着打。
- 区间选择混乱：左闭右闭、左闭右开、左开右闭……别混着用。我个人习惯统一用左闭右开，逻辑更清晰。
💡 一个小技巧：如果你不确定边界怎么写，先画个简单的例子，比如数组 [1, 2, 3]，target = 2。手动模拟一遍循环过程，边界条件就清楚了。
六、总结
二分查找看似简单，但变种问题才是真正的考验。记住三个核心：
- 标准模板：while (left <= right)，mid 防溢出
- 左右边界：左闭右开区间，左边界返回 left，右边界返回 left - 1
- 旋转数组：判断哪一半有序，再决定搜索方向
把这些模板记熟，面试时遇到二分查找的题，你就能从容应对了。