第11篇-二分查找入门-有序数组中的高效搜索技巧

概述：为什么二分查找是算法入门必须掌握的基本功

学完排序之后，下一类非常重要的基础算法就是二分查找。

很多初学者第一次接触二分时，会觉得它很简单：

不就是每次看中间位置，比目标大就往左找，比目标小就往右找吗？

这个理解没错，但只说对了一半。

真正写题时，二分查找最容易出错的地方并不是“思想”，而是这些细节：

• left 和 right 到底表示什么范围
• 循环条件写 left <= right 还是 left < right
• mid 应该怎么计算
• 找到目标后要不要立刻返回
• 查找第一个位置、最后一个位置时边界怎么更新

所以这篇文章的目标，不是只让你会写最基础的二分查找，而是帮你建立一套稳定的二分思维：

学完这篇，你应该能稳定写出二分查找模板，并能解释每一次边界收缩为什么是正确的。

核心概念：二分查找到底在查什么

二分查找解决的是这样一类问题：

在一个有序范围中，通过不断排除一半不可能的答案，快速找到目标位置。

最经典的场景是：

给定一个升序数组 nums 和目标值 target，判断 target 是否存在。

例如：

nums = [1, 3, 5, 7, 9, 11]
target = 7

如果从头到尾一个一个找，最坏情况要看完整个数组，时间复杂度是：

O(n)

但因为数组是有序的，我们可以直接看中间元素：

mid = 5

如果中间元素小于目标值，说明目标值不可能在左边；
如果中间元素大于目标值，说明目标值不可能在右边。

这样每判断一次，就能排除大约一半的数据。

二分查找的前提

二分查找通常需要满足一个关键条件：

搜索空间具有单调性。

最常见的单调性就是数组有序：

• 升序数组
• 降序数组
• 某个条件从 false 逐渐变成 true
• 某个条件从 true 逐渐变成 false

所以不要把二分查找只理解成“在数组里找数”。
它更本质的含义是：

在一个有单调规律的搜索空间里，不断缩小答案范围。

二分查找依赖的不是数组本身，而是搜索空间中存在可以排除一半答案的单调性。

原理：为什么二分查找是 O(log n)

假设数组长度是 n。

普通线性查找每次只能排除一个元素：

n -> n – 1 -> n – 2 -> …

而二分查找每次都能排除一半：

n -> n / 2 -> n / 4 -> n / 8 -> …

当问题规模不断除以 2，直到变成 1 时，大约需要多少次？

答案就是：

log n

例如 n = 1024 时：

1024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

只需要大约 10 次。

这就是二分查找高效的根本原因。

用流程图理解二分

#mermaid-svg-TXgFkRJ2uL00s1Ao{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-TXgFkRJ2uL00s1Ao .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-TXgFkRJ2uL00s1Ao .error-icon{fill:#552222;}#mermaid-svg-TXgFkRJ2uL00s1Ao .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-TXgFkRJ2uL00s1Ao .marker{fill:#333333;stroke:#333333;}#mermaid-svg-TXgFkRJ2uL00s1Ao .marker.cross{stroke:#333333;}#mermaid-svg-TXgFkRJ2uL00s1Ao svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-TXgFkRJ2uL00s1Ao p{margin:0;}#mermaid-svg-TXgFkRJ2uL00s1Ao .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-TXgFkRJ2uL00s1Ao .cluster-label text{fill:#333;}#mermaid-svg-TXgFkRJ2uL00s1Ao .cluster-label span{color:#333;}#mermaid-svg-TXgFkRJ2uL00s1Ao .cluster-label span p{background-color:transparent;}#mermaid-svg-TXgFkRJ2uL00s1Ao .label text,#mermaid-svg-TXgFkRJ2uL00s1Ao span{fill:#333;color:#333;}#mermaid-svg-TXgFkRJ2uL00s1Ao .node rect,#mermaid-svg-TXgFkRJ2uL00s1Ao .node circle,#mermaid-svg-TXgFkRJ2uL00s1Ao .node ellipse,#mermaid-svg-TXgFkRJ2uL00s1Ao .node polygon,#mermaid-svg-TXgFkRJ2uL00s1Ao .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-TXgFkRJ2uL00s1Ao .rough-node .label text,#mermaid-svg-TXgFkRJ2uL00s1Ao .node .label text,#mermaid-svg-TXgFkRJ2uL00s1Ao .image-shape .label,#mermaid-svg-TXgFkRJ2uL00s1Ao .icon-shape .label{text-anchor:middle;}#mermaid-svg-TXgFkRJ2uL00s1Ao .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-TXgFkRJ2uL00s1Ao .rough-node .label,#mermaid-svg-TXgFkRJ2uL00s1Ao .node .label,#mermaid-svg-TXgFkRJ2uL00s1Ao .image-shape .label,#mermaid-svg-TXgFkRJ2uL00s1Ao .icon-shape .label{text-align:center;}#mermaid-svg-TXgFkRJ2uL00s1Ao .node.clickable{cursor:pointer;}#mermaid-svg-TXgFkRJ2uL00s1Ao .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-TXgFkRJ2uL00s1Ao .arrowheadPath{fill:#333333;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-TXgFkRJ2uL00s1Ao .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-TXgFkRJ2uL00s1Ao .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-TXgFkRJ2uL00s1Ao .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-TXgFkRJ2uL00s1Ao .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-TXgFkRJ2uL00s1Ao .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-TXgFkRJ2uL00s1Ao .cluster text{fill:#333;}#mermaid-svg-TXgFkRJ2uL00s1Ao .cluster span{color:#333;}#mermaid-svg-TXgFkRJ2uL00s1Ao div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-TXgFkRJ2uL00s1Ao .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-TXgFkRJ2uL00s1Ao rect.text{fill:none;stroke-width:0;}#mermaid-svg-TXgFkRJ2uL00s1Ao .icon-shape,#mermaid-svg-TXgFkRJ2uL00s1Ao .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-TXgFkRJ2uL00s1Ao .icon-shape p,#mermaid-svg-TXgFkRJ2uL00s1Ao .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-TXgFkRJ2uL00s1Ao .icon-shape .label rect,#mermaid-svg-TXgFkRJ2uL00s1Ao .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-TXgFkRJ2uL00s1Ao .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-TXgFkRJ2uL00s1Ao .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-TXgFkRJ2uL00s1Ao :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

相等

小于 target

大于 target

否

是

确定搜索范围 left 到 right

计算中间位置 mid

nums[mid] 和 target 比较

找到答案

排除左半部分

排除右半部分

更新 left

更新 right

范围是否为空

查找失败

二分查找快，是因为每次判断都不是排除一个元素，而是排除一半搜索空间。

模板一：最基础的二分查找

先看最常见、最适合入门的一种写法：闭区间模板。

所谓闭区间，就是搜索范围始终表示为：

[left, right]

这意味着：

• left 位置可能是答案
• right 位置也可能是答案
• 当 left > right 时，搜索范围为空

基础模板

public static int binarySearch(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;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid – 1;
}
}

return –1;
}

为什么循环条件是 left <= right

因为当前搜索范围是闭区间 [left, right]。

只要 left <= right，这个区间就还有元素：

left == right

时，区间里还有一个元素，也必须检查。

只有当：

left > right

时，才说明范围已经空了。

为什么更新时要写 mid + 1 和 mid – 1

当：

nums[mid] < target

说明 mid 以及 mid 左边都不可能是答案，所以新的搜索范围应该是：

[mid + 1, right]

同理，当：

nums[mid] > target

说明 mid 以及 mid 右边都不可能是答案，所以新的搜索范围应该是：

[left, mid – 1]

这就是闭区间模板里必须写 +1 和 -1 的原因。

闭区间二分的核心是搜索范围始终包含左右端点，所以循环条件是 left <= right，排除 mid 后要更新到 mid + 1 或 mid – 1。

为什么 mid 要写成 left + (right – left) / 2

很多代码里你会看到：

int mid = (left + right) / 2;

这个写法在小数据下通常没问题，但严格来说存在整数溢出风险。

如果 left 和 right 都很大，那么：

left + right

可能超过 int 的最大范围。

更推荐的写法是：

int mid = left + (right – left) / 2;

它和 (left + right) / 2 的数学结果等价，但不会先把两个大数加起来。

取左中位数还是右中位数

上面的写法会取偏左的中点：

mid = left + (right – left) / 2

例如：

left = 0, right = 1
mid = 0

有些二分变形题会使用偏右中点：

int mid = left + (right – left + 1) / 2;

初学阶段先掌握偏左中点即可。
后面遇到特殊边界收缩问题时，再根据区间更新方式选择左中位数或右中位数。

推荐用 left + (right – left) / 2，既能避免溢出，也能让边界含义更清晰。

手动模拟：二分查找一次完整过程

来看一个具体例子。

nums = [1, 3, 5, 7, 9, 11, 13]
target = 9

初始范围：

left = 0, right = 6

第一次：

mid = 3
nums[mid] = 7

因为 7 < 9，所以目标值一定在右边：

left = 4, right = 6

第二次：

mid = 5
nums[mid] = 11

因为 11 > 9，所以目标值一定在左边：

left = 4, right = 4

第三次：

mid = 4
nums[mid] = 9

找到答案，返回下标 4。

这个过程可以写成表格：

手动模拟非常重要。
当你写二分边界不确定时，拿一个长度为 1、2、3 的数组跑一遍，很多错误会立刻暴露。

模板二：查找第一个等于目标值的位置

基础二分只要求“找到就行”。
但很多题并不只问目标值是否存在，而是问：

第一个等于 target 的位置在哪里？

例如：

nums = [1, 2, 2, 2, 3, 4]
target = 2

普通二分可能返回下标 1、2 或 3，但如果题目要求第一个位置，答案必须是：

1

这时就不能找到后立刻返回，而是要继续向左搜索。

左边界模板

public static int searchFirst(int[] nums, int target) {
int left = 0;
int right = nums.length – 1;
int ans = –1;

while (left <= right) {
int mid = left + (right – left) / 2;

if (nums[mid] >= target) {
if (nums[mid] == target) {
ans = mid;
}
right = mid – 1;
} else {
left = mid + 1;
}
}

return ans;
}

为什么找到后还要继续往左

当：

nums[mid] == target

只能说明当前位置是一个答案，但不一定是最左边的答案。

所以我们先记录：

ans = mid;

然后继续收缩右边界：

right = mid – 1;

这样才能继续查找更靠左的目标值。
找第一个目标值时，遇到 target 不能急着返回，而要记录答案并继续向左压缩搜索范围。

模板三：查找最后一个等于目标值的位置

和左边界对应，右边界查找要解决的是：

最后一个等于 target 的位置在哪里？

还是这个数组：

nums = [1, 2, 2, 2, 3, 4]
target = 2

最后一个 2 的下标是：

3

右边界模板

public static int searchLast(int[] nums, int target) {
int left = 0;
int right = nums.length – 1;
int ans = –1;

while (left <= right) {
int mid = left + (right – left) / 2;

if (nums[mid] <= target) {
if (nums[mid] == target) {
ans = mid;
}
left = mid + 1;
} else {
right = mid – 1;
}
}

return ans;
}

左边界和右边界的区别

可以用一句话记：

• 找左边界：遇到目标后继续往左找
• 找右边界：遇到目标后继续往右找

也可以对比表格：

找最后一个目标值时，遇到 target 要记录答案，并继续向右搜索更靠后的目标值。

经典例题一：搜索插入位置

题目大意：

给定一个升序数组和目标值 target，如果目标值存在，返回下标；如果不存在，返回它应该插入的位置。

例如：

nums = [1, 3, 5, 6]
target = 5
答案：2

nums = [1, 3, 5, 6]
target = 2
答案：1

这题的本质

它其实是在找：

第一个大于等于 target 的位置。

如果这个位置存在，就是目标值的位置或插入位置；
如果所有元素都小于 target，那就应该插入到数组末尾。

代码实现

public static int searchInsert(int[] nums, int target) {
int left = 0;
int right = nums.length – 1;
int ans = nums.length;

while (left <= right) {
int mid = left + (right – left) / 2;

if (nums[mid] >= target) {
ans = mid;
right = mid – 1;
} else {
left = mid + 1;
}
}

return ans;
}

为什么 ans 初始化为 nums.length

如果数组中没有任何元素大于等于 target，说明目标值应该插入到最后：

nums = [1, 3, 5, 6]
target = 7

这时答案应该是：

4

也就是 nums.length。

所以 ans 初始化为 nums.length 是合理的默认答案。

搜索插入位置不是简单找相等，而是在找第一个大于等于目标值的位置。

经典例题二：在排序数组中查找元素的第一个和最后一个位置

题目大意：

给定一个升序数组 nums 和目标值 target，返回目标值在数组中的开始位置和结束位置。

如果不存在，返回：

[-1, -1]

例如：

nums = [5, 7, 7, 8, 8, 10]
target = 8
答案：[3, 4]

这道题非常适合练习左右边界。

代码实现

public static int[] searchRange(int[] nums, int target) {
int first = searchFirst(nums, target);
int last = searchLast(nums, target);
return new int[]{first, last};
}

private static int searchFirst(int[] nums, int target) {
int left = 0;
int right = nums.length – 1;
int ans = –1;

while (left <= right) {
int mid = left + (right – left) / 2;

if (nums[mid] >= target) {
if (nums[mid] == target) {
ans = mid;
}
right = mid – 1;
} else {
left = mid + 1;
}
}

return ans;
}

private static int searchLast(int[] nums, int target) {
int left = 0;
int right = nums.length – 1;
int ans = –1;

while (left <= right) {
int mid = left + (right – left) / 2;

if (nums[mid] <= target) {
if (nums[mid] == target) {
ans = mid;
}
left = mid + 1;
} else {
right = mid – 1;
}
}

return ans;
}

这题为什么不能线性扫描

线性扫描当然也能做，但时间复杂度是：

O(n)

题目如果要求：

O(log n)

那就必须利用数组有序这个条件。
而有序数组里查找边界，正是二分查找最典型的应用。

时间复杂度：

O(log n)

空间复杂度：

O(1)

经典例题三：寻找峰值

有些题看起来不像传统的“有序数组查找”，但仍然可以用二分。

例如寻找峰值：

峰值元素是指比相邻元素都大的元素，给定数组 nums，返回任意一个峰值下标。

假设：

nums[-1] = nums[n] = -∞

为什么这题可以二分

观察 nums[mid] 和 nums[mid + 1]：

• 如果 nums[mid] < nums[mid + 1]，说明右边一定存在峰值
• 如果 nums[mid] > nums[mid + 1]，说明左边或当前位置一定存在峰值

这不是传统的有序数组，但仍然存在可以排除一半搜索空间的规律。

代码实现

public static int findPeakElement(int[] nums) {
int left = 0;
int right = nums.length – 1;

while (left < right) {
int mid = left + (right – left) / 2;

if (nums[mid] < nums[mid + 1]) {
left = mid + 1;
} else {
right = mid;
}
}

return left;
}

为什么这里是 left < right

这段代码维护的是一个候选区间。
当区间只剩一个位置时，这个位置就是答案，所以循环条件写成：

while (left < right)

而不是 left <= right。

同时这里有一个关键点：

right = mid;

不是：

right = mid – 1;

因为当 nums[mid] > nums[mid + 1] 时，mid 自己就可能是峰值，不能直接排除。

二分不只用于完全有序数组，只要能根据中点判断某一半一定存在答案，就可以考虑二分。

二分查找常见模板怎么选择

初学阶段最容易被各种模板搞混。
建议先从下面这张表建立判断。

不要一开始就背很多风格完全不同的模板。
更推荐的学习方式是：

二分模板的核心不是记住形式，而是明确搜索区间含义，以及每次更新时有没有排除 mid。

易错点：新手写二分最容易踩的坑

1. 没想清楚区间含义就开始写

你必须先明确：

[left, right]

还是：

[left, right)

如果区间含义不清楚，循环条件和边界更新一定会混乱。

2. left <= right 和 left < right 混用

闭区间查找某个值时，通常是：

while (left <= right)

候选区间收敛到一个点时，常见写法是：

while (left < right)

它们不是随便替换的。

3. 更新边界时忘记排除 mid

基础查找中，如果 nums[mid] < target，说明 mid 已经不可能是答案，必须写：

left = mid + 1;

如果写成：

left = mid;

在某些情况下会死循环。

4. 找边界时找到目标就直接返回

如果题目问的是第一个位置或最后一个位置，找到 target 只能说明当前是一个候选答案，不能直接返回。

5. 没有处理空数组

如果数组为空：

nums.length = 0

那么：

right = nums.length – 1

会变成 -1。
闭区间模板下循环不会执行，通常可以自然返回 -1，但你要知道这个边界是怎么工作的。

6. mid + 1 越界访问

像寻找峰值这类题会访问：

nums[mid + 1]

所以必须保证循环条件和 mid 计算让 mid + 1 合法。
在 while (left < right) 中，mid 一定小于 right，因此 mid + 1 不会越界。

7. 忽略重复元素

有重复元素时，普通二分找到的下标不一定固定。
如果题目要求最左或最右，就必须使用边界查找。

复杂度总结：二分查找为什么适合大数据量

二分查找的时间复杂度通常是：

O(log n)

空间复杂度通常是：

O(1)

如果写成递归形式，递归栈会带来：

O(log n)

的额外空间。
但在数组查找中，更推荐使用迭代写法。

对比一下：

当数据量很大时，O(log n) 的优势非常明显。
例如一百万个元素，二分大约只需要二十次左右的比较。

二分查找用有序性换来了每次排除一半搜索空间的能力，所以在大规模查找问题中非常高效。

总结

二分查找真正难在边界，而不是思想。
二分查找的核心不是背模板，而是理解每一次比较后，为什么可以安全地丢掉一半搜索空间。
当你能稳定掌握这个思路后，下一篇的“二分答案法”会更容易理解。
因为二分答案的本质，也是把一个最优值问题转化成在答案范围上的二分查找。