LeetCode 704. 二分查找
目录
题目描述
题意分析
在一个升序排列、元素互不相同的整数数组里找
target，找到返回它的下标，找不到返回-1。题目还明确要求算法的时间复杂度是 $O(\log n)$，这句话直接把「从头扫到尾」排除掉了。「有序」是全题唯一的算法前提，也是唯一可以利用的结构。 有序意味着比较任意一个位置
mid上的值与target，都能得到一个覆盖半个数组的结论：若nums[mid] < target，那么由升序可知mid及其左边的所有元素都小于target，它们全都不可能是答案；若nums[mid] > target，同理mid及其右边全部作废。换句话说，一次比较的信息量是「排除一半」，而不是「排除一个」——这正是对数复杂度的来源。这里真正被用到的性质是单调性：判定式「nums[i] < target」沿着下标从左到右只会从真变假、不会来回摇摆，因此存在一个明确的分界点。任何丢掉单调性的输入（哪怕只是把两个元素调换位置）都会让这套推理立即失效。「元素互不相同」这个条件让问题变得简单：命中即答案，不需要考虑「返回哪一个」。一旦允许重复，命中之后还得继续向左或向右收缩才能定位首末位置，那已经是另一类问题了。
需要留意的边界情形：数组只有一个元素（最容易暴露「少检查一次」的收尾错误）；
target比所有元素都小或都大；target恰好落在两个相邻元素之间。后两种都属于「不存在」的情形，必须稳定地返回-1，不能返回其他编码值。
解法：闭区间二分查找
核心思路
闭区间
[left, right]表示仍可能包含target的范围。比较中点后，利用数组升序性排除中点及一侧；区间为空仍未命中时返回-1。
解题步骤
- 初始化
left = 0、right = nums.length - 1。- 当
left <= right时计算中点mid。- 命中就返回
mid；目标较大则令left = mid + 1，否则令right = mid - 1。- 循环结束说明目标不存在，返回
-1。
代码实现
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
func search(nums []int, target int) int {
left, right := 0, len(nums)-1
for left <= right {
mid := left + (right-left)/2
if nums[mid] == target {
return mid
}
if nums[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return -1
}
复杂度分析
- 时间复杂度：$O(\log n)$，每轮排除约一半候选。
- 空间复杂度：$O(1)$。
关键点总结
- 闭区间写法必须配套使用
right = n - 1、left <= right和mid ± 1。- 中点写成
left + (right - left) / 2，避免加法溢出。- 每次更新都排除已经检查过的
mid，保证区间持续缩小。
易错点总结
- 把循环条件写成
left < right，会漏查最后一个位置。- 把右边界初始化为数组长度，会访问越界。
- 更新为
left = mid或right = mid，可能导致死循环。- 未找到时应返回
-1，不要误返回插入位置left。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 元素可重复，命中后不能立刻返回，要把「找到即停」改成两次「找边界」的二分 |
| 35. 搜索插入位置 | 简单 | 未命中时要求返回插入位置，答案正好是本题循环退出后的 left，收尾不同而循环体完全一致 |
| 278. 第一个错误的版本 | 简单 | 没有数组可读，单调性来自「一旦是坏版本后面全坏」的判定函数，还要额外优化调用次数 |
| 367. 有效的完全平方数 | 简单 | 二分的对象是候选答案而不是数组下标，判定要算平方并防止溢出，只需回答存在与否 |
| 540. 有序数组中的单一元素 | 中等 | 没有 target 可比，单调量是「配对是否错位」，mid 需要先对齐到偶数下标才能比较 |
| LCR 068. 搜索插入位置 | 简单 | 与 35 同题换号，适合专门练「插入位置 = 小于 target 的元素个数」这个等价说法 |
| LCR 070. 有序数组中的单一元素 | 中等 | 与 540 同题换号，重点在于说明为什么线性异或不满足对数复杂度要求 |
| 剑指 Offer 53 - I. 在排序数组中查找数字 I | 简单 | 要的是出现次数而非下标，需要左右边界各二分一次再相减，比本题多一层边界推导 |
| 剑指 Offer 53 - II. 0～n-1中缺失的数字 | 简单 | 判定式换成 nums[mid] == mid，利用的是下标与值的对应关系而不是与外部目标比较 |
| 面试题 10.05. 稀疏数组搜索 | 简单 | 数组中夹有空字符串，mid 处可能无法比较，必须先线性挪开空串，最坏复杂度因此退化成线性 |