二分查找 图解题解
升序数组找目标值，从头挨个扫等于白浪费「有序」这张牌——每次取中间一比，范围对折，O(log n) 就够了。
像猜数字游戏里的高手：每次都猜正中间那个数，对方说「大了」就扔掉右半边，说「小了」就扔掉左半边——每问一次，范围砍一半。100 万个数最多猜 20 次就能锁定，而不是傻乎乎从头一个个试。有序是先决条件，正中间就是每次的「分水岭」，比目标小则答案在右，比目标大则在左，不可能跑到另一边。
这道题到底在问什么
- nums
- [1, 3, 5, 7, 9, 11]
- target
- 9
- 输出
- 4
先想最直接的笨办法
最直接：从下标 0 挨个比，碰到 9 就返回。可这样要扫到下标 4，6 个数比 5 次；一百万个数最坏比一百万次。题目都把有序明牌摆你面前了，却还从头扫，等于白白浪费了这个条件。（动画第 3 步）
最优解：一步一步想明白
- 3最直接：从下标 0 挨个比，碰到 9 就返回。可这样要扫到下标 4，6 个数比 5 次；一百万个数最坏比一百万次。题目都把有序明牌摆你面前了，却还从头扫，等于白白浪费了这个条件。
- 4转折：因为数组有序，正中间那个数就是一道分水岭。用 l、r 圈出范围，mid 取正中间——这是不变量：mid 处的数比 target 小，target 只可能在它右边；比 target 大，只可能在左边。所以每比一次就能整段丢掉一半，不用回头扫。
- 5l=0, r=5左指针 l=0，右指针 r=5，范围就是整个数组。要找的 target = 9。
- 6mid = (0+5)//2 = 2中间下标 mid = (0+5)//2 = 2，nums[2] = 5。拿它和目标 9 比一比。
- 75 小于 9 → 丢左半5 比 9 小。因为右边全都更大，9 只可能在 mid 右边，mid 这个 5 本身也不是答案——左半连 mid 一起，整段可以扔了。
- 8l = mid+1 = 3把左指针跳到 mid+1 = 3，下标 0、1、2（含那个 5）整段灰掉丢弃。范围缩到 [3, 5]，只剩一半。
- 9mid = (3+5)//2 = 4新范围 [3, 5]，新的中间 mid = (3+5)//2 = 4，nums[4] = 9。再和目标 9 比。
- 10nums[4] == 9nums[4] 正好等于 9，命中！返回下标 4。从 6 个数里只比了 2 次就找到——这就是砍半的威力。
- 11找 target = 6换个例子：找 6。数组里根本没有 6，看二分怎么干净地收尾、返回 -1。
- 125 小于 6 → l=3mid=2 处是 5，比 6 小，丢左半，l 跳到 3。范围 [3, 5]。
- 139 大于 6 → r=3mid=4 处是 9，比 6 大，这回丢右半，r 收到 mid−1 = 3。现在 l 和 r 都指向 3。
- 14r=2，l 大于 r 结束mid=3 处是 7，比 6 大，r 收到 2。这下 l(3) 越过了 r(2)，范围空了，循环结束——全程没碰到 6，返回 -1。
- 15若 l=mid 会原地不动雷区实演：只剩 [1, 3] 找 3。mid=0 处是 1，偏小，本该把 l 跳到 mid+1。可要是手滑写成 l=mid，l 还是 0，下一轮 mid 算出来又是 0，区间永远不缩——卡死。所以收缩一定要跳过 mid：l=mid+1 或 r=mid−1。
- 18只要数据有序（或答案有单调性），就该想二分：搜索插入位置、x 的平方根、爱吃香蕉的珂珂，全是它的变形。
- 25这套 l/mid/r 是一整类题的骨架：LC35 搜索插入位置（找不到返回 l）、LC34 找左右边界，再进阶到「二分答案」LC875 爱吃香蕉的珂珂、LC1011 运送包裹——只要答案有单调性就能二分。更多在 二分查找专题 继续，也可以让小欧帮你讲透「为什么只要单调就能砍半」。
⚠️ 容易写错的地方
✗ 错：while l 小于 r（漏等号）
✓ 对：while l 小于等于 r
闭区间下区间剩一个元素时 l==r，漏等号会跳过它，该元素正好是答案就找不到
✗ 错：l = mid 或 r = mid（不动）
✓ 对：l = mid+1 / r = mid-1
mid 已比过、不是答案，不 +1/-1 会卡在原地，区间不缩小，死循环
✗ 错：mid = (l+r)//2
✓ 对：mid = l + (r−l)//2
超大数组里 l+r 可能整数溢出；改成 l 加上半个区间宽度，永不溢出，结果一样
完整代码（Python / C++ / Java）
Python
class Solution:
def search(self, nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target: return mid
if nums[mid] < target: l = mid + 1 # 丢左半
else: r = mid - 1 # 丢右半
return -1C++
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = (int)nums.size() - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
}
};Java
class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (nums[mid] == target) return mid;
if (nums[mid] < target) l = mid + 1;
else r = mid - 1;
}
return -1;
}
}套路模板 · 闭区间二分（铁律）
# 闭区间[l,r]：区间里每个位置都还可能是答案
l, r = 0, len(nums) - 1
while l <= r: # 铁律1：带等号
mid = l + (r - l) // 2 # 铁律2：防溢出
if check(mid): return mid # 命中条件按题改
elif nums[mid] < target:
l = mid + 1 # 铁律3：跳过 mid
else:
r = mid - 1 # 铁律3：跳过 mid
return -1 # 区间清空仍没中// 闭区间[l,r]：区间里每个位置都还可能是答案
int l = 0, r = (int)nums.size() - 1;
while (l <= r) { // 铁律1：带等号
int mid = l + (r - l) / 2; // 铁律2：防溢出
if (check(mid)) return mid; // 命中条件按题改
else if (nums[mid] < target) l = mid + 1; // 铁律3：跳过 mid
else r = mid - 1; // 铁律3：跳过 mid
}
return -1;// 闭区间[l,r]：区间里每个位置都还可能是答案
int l = 0, r = nums.length - 1;
while (l <= r) { // 铁律1：带等号
int mid = l + (r - l) / 2; // 铁律2：防溢出
if (check(mid)) return mid; // 命中条件按题改
else if (nums[mid] < target) l = mid + 1; // 铁律3：跳过 mid
else r = mid - 1; // 铁律3：跳过 mid
}
return -1;复杂度
时间复杂度
O(log n)
每轮把搜索范围砍掉一半，n→n/2→n/4…
空间复杂度
O(1)
只用 l、r、mid 三个指针，没开额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 二分查找 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
mid 为什么写 l+(r−l)//2，不写 (l+r)//2？+
两者数值一样，但 l+r 在超大数组里可能整数溢出；写成 l 加上半个区间宽度就永远不会溢出，是更安全的写法。
循环条件用「小于」还是「小于等于」？+
闭区间 [l, r] 必须用小于等于。因为 l==r 时区间里还剩一个候选，用「小于」会直接跳过它，正好是答案就漏掉了。
数组无序也能二分吗？+
不能直接二分，得先排序。但更本质的前提是答案有单调性——猜数字、爱吃香蕉的珂珂这类题虽不是排好序的数组，照样能二分。
闭区间和左闭右开怎么选？+
两套都对，关键是配套：闭区间用 l 小于等于 r、收缩 mid±1；左闭右开用 l 小于 r、r=mid。别混搭，混了就出 bug。本题用闭区间最直观。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。