#704
简单
中频
二分查找二分查找
这是一道围绕数组、二分查找展开的高频练习。建议先掌握「二分查找」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
数组
二分查找
题目分析
给你一个升序排列的数组和目标值 target。
要求你在数组里找到这个目标值的下标；如果不存在，就返回 -1。
一句话概括：
每次利用有序性，把搜索区间砍掉一半。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：在有序数组上维护闭区间
[left, right]，每次看中点后砍掉一半搜索范围。推荐代码
推荐解法：二分查找
时间复杂度： O(log n)
空间复杂度： O(1)
核心思路： 在有序数组上维护闭区间
[left, right]，每次看中点后砍掉一半搜索范围。
class Solution {
public int search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (right - left) / 2 + left;
int num = nums[mid];
if (num == target) {
return mid;
} else if (num > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
结构化讲解
面试时怎么讲
开场思路
这是有序数组查找，我会直接用二分。关键是先把搜索区间定义清楚。
核心过程
- 我维护闭区间
[left, right]，初始覆盖整个数组。 - 每轮取中点
mid和目标值比较。 - 如果命中直接返回；否则利用有序性判断保留左半还是右半，并把
mid排除出新区间。 - 当
left > right时结束，说明目标不存在。
复杂度总结
时间复杂度 O(log n)，空间复杂度 O(1)。
面试补一句：二分题最怕的是边界定义前后不一致，所以先讲区间，再讲代码。
核心思路
二分查找真正的难点不是会不会写模板，而是区间定义、循环条件、边界更新三件事必须完全一致。只要这三者统一，代码就会稳定。
步骤讲解
1
先定义搜索区间
这里使用闭区间 [left, right]，初始覆盖整个数组。
为什么这样做：只有先把区间定义讲清楚，后面的循环条件和边界更新才不会互相打架。
对应代码提示：int left = 0, right = nums.length - 1;
2
每轮计算中点
取 mid = left + (right - left) / 2 作为当前比较位置。
为什么这样做：中点把当前区间一分为二，也是利用有序性裁剪搜索范围的依据。
对应代码提示：int mid = left + (right - left) / 2;
3
比较中点值和目标值
如果 nums[mid] == target 直接返回，否则判断目标在左半还是右半。
为什么这样做：数组有序，所以和中点的大小关系足以决定哪一半可以整体丢弃。
对应代码提示：if (nums[mid] == target) return mid;
4
按区间定义更新边界
若目标在右半区，就令 left = mid + 1；否则令 right = mid - 1。
为什么这样做：因为
mid 已经比较过，所以新的区间必须把它排除掉。对应代码提示：left = mid + 1; 或 right = mid - 1;
5
区间空了就结束
当 left > right 时，说明搜索区间已经为空，目标不存在。
为什么这样做：闭区间语义下，
left <= right 才表示还有候选元素。对应代码提示：while (left <= right) { ... }
易错点
区间定义和循环条件不一致
比如你心里按闭区间写，循环却用开区间逻辑，最后一定会出现死循环或漏解。
正确理解：先选定一种区间定义，再让循环条件和边界更新完全配套。
边界更新没有排除 mid
如果写成 left = mid 或 right = mid，当区间只剩两个元素时很容易卡住。
正确理解：闭区间写法下，比较过
mid 后必须更新为 mid + 1 或 mid - 1。忘记题目前提是有序数组
二分成立的根本原因是有序性；数组无序时，裁掉一半区间没有任何依据。
正确理解：面试中先明确说明：这个做法成立的前提是数组已经有序。
复杂度与适用判断
时间复杂度：O(log n)
空间复杂度：O(1)
比其他方案更好在哪里：比线性扫描快得多，尤其适合规模大的有序数组。
适用判断：凡是“有序 + 查找某个边界或目标”的问题，都要先检查能不能转成二分。
额外提醒
- 二分不是单独的技巧，而是一套“区间定义 + 比较 + 更新”的完整协议。
- 只要协议统一，变形题也只是修改判断条件，不是重写思路。
动画演示
如果你还没完全看懂，可以展开动画演示。
二分查找动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
二分查找动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入有序数组和目标值，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。