目录

核心思想

算法定义

核心本质：二段性（比"必须有序"更准确的表述）

时间复杂度

⼆分查找（easy）

在排序数组中查找元素的第⼀个和最后⼀个位置（medium）

1.查找区间左端点

处理细节

求中点

​编辑​编辑

2.查找区间右端点

处理细节

求中点

最后附上模板：​编辑

x的平⽅根（easy）

搜索插⼊位置（easy）

⼭峰数组的峰顶（easy）

解法（二分查找）

寻找峰值（medium）

解法（二分查找算法）

情况一：nums[mid] > nums[mid+1]（mid 处在"下降"趋势）

情况二：nums[mid] < nums[mid+1]（mid 处在"上升"趋势）

搜索旋转排序数组中的最⼩值（medium）

解法（二分查找）

0〜n-1中缺失的数字（easy）

解法（二分查找算法）

LCR 173. 点名 —— 四种 O(n) 解法详解

解法一：哈希表

解法二：直接遍历找结果

解法三：位运算（异或 XOR）

解法四：数学（高斯求和公式）

四种解法对比总表

核心思想

一个生活例子

猜数字游戏：我心里想了一个 1~100 之间的数，你来猜。

• 你猜 50 → 我说"大了"

• 你猜 25 → 我说"小了"

• 你猜 37 → 我说"大了"

• 你猜 31 → 我说"对了！"

你每次都猜中间值，每次排除一半的可能性。这就是二分查找的核心思想。100 个数字，最多猜 7 次就能猜中（因为 2^7 = 128 > 100）。而如果从头到尾一个一个猜，最多要 100 次。

算法定义

在一个有序序列中，每次取中间元素与目标值比较，如果中间元素等于目标值则找到；如果中间元素大于目标值，则在左半部分继续查找；如果中间元素小于目标值，则在右半部分继续查找。重复此过程直到找到目标值或搜索区间为空。

关键前提

核心本质：二段性（比"必须有序"更准确的表述）

很多教材说"二分查找必须用于有序数组"，这个说法不准确。"有序"只是二分查找的充分条件，不是必要条件。

什么是二段性？

二段性是指：存在一个判定条件 P，使得数组被 P 分成两段连续的区间——一段满足 P，一段不满足 P。这样每次取 mid 判断 P，就能确定性地排除一半，在另一半中继续查找。

数组: [ F F F F T T T T ]
↑ ↑
P=false 的段 P=true 的段
​
取 mid 判断 P(mid)：
- P(mid) = false → mid 在左段，答案在右段 → 舍去左半
- P(mid) = true → mid 在右段，答案在左段（含 mid）→ 舍去右半

为什么"有序"只是充分条件？

因为有序数组天然具有二段性。在升序数组中找 target，定义判定函数P(i) = (nums[i] >= target)：

升序: [1, 3, 5, 7, 9, 11], target = 6
P: F F F T T T
↑
第一个 >= 6 的位置 = lower_bound

因为数组有序，>= target的元素一定连续出现在右边，< target的元素连续出现在左边，自然形成两段。有序保证了二段性，但二段性不一定需要有序。

无序但有二段性的经典例子

例子 1：寻找峰值（LeetCode 162）

nums = [1, 2, 3, 1]
​
完全无序！但定义 P(i) = (nums[i] < nums[i+1])：
P: T T F F
↑ ↑
上升段(T) 下降段(F)
​
取 mid，如果 P(mid)=T → 右边有峰值 → 舍去左半
如果 P(mid)=F → 左边有峰值 → 舍去右半

例子 2：旋转排序数组找最小值（LeetCode 153）

nums = [4, 5, 6, 7, 0, 1, 2]
​
不是升序！但定义 P(i) = (nums[i] > nums[right])：
P: T T T T F F F
↑ ↑
大于右端的段 小于等于右端的段
​
取 mid，如果 P(mid)=T → 最小值在 mid 右边 → 舍去左半
如果 P(mid)=F → 最小值在 mid 及左边 → 舍去右半

例子 3：山脉数组找峰顶（LeetCode 852）

nums = [0, 2, 4, 6, 5, 3, 1]
​
定义 P(i) = (nums[i] < nums[i+1])：
P: T T T F F F
↑ ↑
上坡段(T) 下坡段(F)

二段性 vs 有序性

理解了二段性，面对一道题时不要问"数组有序吗"，而要问：

"我能否找到一个判定条件，使得每次取 mid 都能确定性地排除一半？"

如果能，就能用二分。这才是二分查找最本质的前提。

时间复杂度

每次将搜索范围缩小一半：n → n/2 → n/4 → ... → 1，共 log₂n 步。

⼆分查找（easy）

704. 二分查找 - 力扣（LeetCode）

最简单的二分查找

在排序数组中查找元素的第⼀个和最后⼀个位置（medium）

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

利用二段性，找左右端点。分别对应target的begin和end位置

1.查找区间左端点

左端点里，左边全是 < target，右边全是 > =target的.把数组分成了两部分

处理细节

1，循环条件：我们选择left<right而不是left<=right.

解释：

a.当直接有结果的时候，也就是left=right的时候，就已经得到了最终结果，此时无需再进入循环判断

b.当值全大于target的时候，我们的right需要左移到与left相遇为止，也就是上面第1步中的查找左端 里的第2中情况，也就是left=right的时候，就已经得到了最终结果，此时无需再进入循环判断

c.当值全小于target的时候，我们的left需要右移到与right相遇为止，也就是上面第1步中的查找左端 里的第1中情况，也就是left=right的时候，就已经得到了最终结果，此时无需再进入循环判断

总结一下，二分查找是非常容易写出死循环代码的，所以我们要把控好细节问题，比如a情况，假如我们进入了循环，且循环条件错误的设置为了left<=right，那么会导致right=mid，此后一直判断一直right=mid，一直死循环下去

求中点

原本是有两种写法的

但此处需要考虑特殊情况：当数据剩余最后两个元素的时候

a.选用上图中的第1种情况才是正确的求中点操作，此时求出的mid为靠左边的数

此时若命中条件1，left右移，不满足判断条件，跳出循环，程序正常结束

若此时命中条件2，right左移，不满足判断条件，跳出循环，程序正常结束

b.若选用上图中的第2种情况时，此时求出的mid为靠右边的数，该种情况会导致进入死循环：

此时如果判断命中了条件1，此时left右移动到mid+1，此时程序结束

但此时如果判断命中了条件2，此时会发现right原地不动，当下次进入循环的时候，判断后依旧保持原样，此时进入了死循环

2.查找区间右端点

处理细节

循环条件同左端点里的解释：left<right

求中点

分析和求左端点里是类似的，这里必须用left+(right-left+1)/2，否则会陷入死循环

最后附上模板：

x的平⽅根（easy）

69. x 的平方根 - 力扣（LeetCode）

思考出if条件后，走模板即可

搜索插⼊位置（easy）

35. 搜索插入位置 - 力扣（LeetCode）

思路：分析发现，实际要做的工作可以合并成找出大于等于target的那个数或者位置。

可以利用二段性

⼭峰数组的峰顶（easy）

852. 山脉数组的峰顶索引 - 力扣（LeetCode）

解法（二分查找）

算法思路：

1. 分析峰顶位置的数据特点，以及山峰两旁的数据的特点：
   a. 峰顶数据特点：arr[i] > arr[i - 1] && arr[i] > arr[i + 1] ；
   b. 峰顶左边的数据特点：arr[i] > arr[i - 1] && arr[i] < arr[i + 1] ，也就是呈现上升趋势；
   c. 峰顶右边数据的特点：呈现下降趋势。

2. 因此，根据 arr[i] < arr[i - 1] && arr[i] > arr[i + 1] ，也就是 mid 位置的信息，我们可以分为下面的情况：
   a. 如果 mid 位置呈现上升趋势，说明我们接下来要在 [mid + 1, right] 区间继续搜索；
   b. 如果 mid 位置呈现下降趋势，说明我们接下来要在 [left, mid - 1] 区间搜索；
   c. 如果 mid 位置就是山峰，直接返回结果。

寻找峰值（medium）

162. 寻找峰值 - 力扣（LeetCode）

解法（二分查找算法）

算法思路：寻找二段性：任取一个点 i ，与下一个点 i + 1 ，会有如下两种情况：

1. arr[i] > arr[i + 1] ：此时左侧区域一定会存在山峰（因为最左侧是负无穷），那么我们可以去左侧去寻找结果；

2. arr[i] < arr[i + 1] ：此时右侧区域一定会存在山峰（因为最右侧是负无穷），那么我们可以去右侧去寻找结果。

当我们找到二段性的时候，就可以尝试用二分查找算法来解决问题。

可以分析出下面的情况，然后根据这两个if条件就能写出代码了

我们比较nums[mid]和nums[mid+1]，只有两种情况：

情况一：nums[mid] > nums[mid+1]（mid 处在"下降"趋势）

nums[mid] \ \ nums[mid+1] \

mid 位置本身就是一个下降点。这意味着峰值要么就是 mid，要么在 mid 左边。mid 右边不可能有峰值（因为 mid 到 mid+1 已经在下降了），但我们不确定 mid 自己是不是峰值——它可能左边还有更高的。

所以：right = mid（保留 mid，因为 mid 本身可能就是答案）

情况二：nums[mid] < nums[mid+1]（mid 处在"上升"趋势）

nums[mid+1] / / nums[mid] /

mid 位置在上升，说明mid 本身一定不是峰值（它右边的邻居比它大）。峰值一定在 mid 右边。

所以：left = mid + 1（跳过 mid，因为 mid一定不是答案）

搜索旋转排序数组中的最⼩值（medium）

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

解法（二分查找）

算法思路：题目中的数组规则如下图所示，其中 C 点就是我们要求的点（图片中的n-1表示的是最后一个位置的值，我们都是用最后一个位置的值来做比较的）：

二分的本质：找到一个判断标准，使得查找区间能够一分为二。

通过图像我们可以发现，[A，B] 区间内的点都是严格大于 D 点的值的，C 点的值是严格小于 D 点的值的。但是当 [C，D] 区间只有一个元素的时候，C 点的值是可能等于 D 点的值的。因此，初始化左右两个指针 left ， right ：然后根据 mid 的落点，我们可以这样划分下一次查询的区间：

1. 当 mid 在 [A，B] 区间的时候，也就是 mid 位置的值严格大于 D 点的值，下一次查询区间在 [mid + 1，right] 上；

2. 当 mid 在 [C，D] 区间的时候，也就是 mid 位置的值严格小于等于 D 点的值，下次查询区间在 [left，mid] 上。

当区间长度变成 1 的时候，就是我们要找的结果。

0〜n-1中缺失的数字（easy）

LCR 173. 点名 - 力扣（LeetCode）

解法（二分查找算法）

算法思路：关于这道题中，时间复杂度为 O(N) 的解法有很多种，这里直接上手最优解，其他解法末尾会讲到的。讲一个最优的二分法，来解决这个问题。在这个升序的数组中，我们发现：

1. 在第一个缺失位置的左边，数组内的元素都是与数组的下标相等的；

2. 在第一个缺失位置的右边，数组内的元素与数组下标是不相等的。

因此，我们可以利用这个二段性，来使用二分查找算法。

LCR 173. 点名 —— 四种 O(n) 解法详解

某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组records。假定仅有一位同学缺席，请返回他的学号。

示例：

输入:records = [0, 1, 2, 3, 5]→ 输出: 4

输入:records = [0, 1, 2, 3, 4, 5, 6, 8]→ 输出: 7

关键信息：

• 数组是升序的

• 学号从 0 开始连续编号

• 恰好缺一个人

• 缺失的可能在中间，也可能在末尾（如[0,1,2,3]缺 4）

解法一：哈希表

思路：把数组中所有出现过的学号存入哈希表，然后从 0 开始逐个检查哪个学号不在哈希表中。

int takeAttendance(vector<int>& records) { unordered_set<int> seen; for (int r : records) { seen.insert(r); // 把所有出现的学号存入哈希表 } ​ for (int i = 0; i <= records.size(); i++) { if (seen.find(i) == seen.end()) { return i; // 第一个不在哈希表中的就是缺席的 } } return -1; }

执行过程演示：

records = [0, 1, 2, 3, 5]

第1步: 建哈希表，seen = {0, 1, 2, 3, 5}

第2步: 从 0 开始逐个检查：

• i=0: 在 seen 中 ✓

• i=1: 在 seen 中 ✓

• i=2: 在 seen 中 ✓

• i=3: 在 seen 中 ✓

• i=4: 不在 seen 中 → 返回 4 ✓

复杂度：时间 O(n)（遍历建表 + 遍历查找），空间 O(n)（哈希表存储 n 个元素）

优缺点：

• 优点：最直觉、最通用。即使数组无序也能用

• 缺点：空间复杂度 O(n)，多了一次遍历，效率最低

能写出来说明你懂基础数据结构，但面试官可能会追问"能不能不用额外空间？"

解法二：直接遍历找结果

思路：因为数组升序且学号从 0 开始连续编号，所以正常情况下records[i]应该等于i。第一个records[i] != i的位置，缺失的就是i。如果全部相等，缺失的就是最后一个（records.size()）。

int takeAttendance(vector<int>& records) { for (int i = 0; i < records.size(); i++) { if (records[i] != i) { return i; // 第一个"学号和下标不匹配"的位置 } } return records.size(); // 都匹配，缺的是最后一个 }

执行过程演示：

例1: records = [0, 1, 2, 3, 5]

i=4 时 records[4]=5 ≠ 4 → 返回 4 ✓

例2: records = [0, 1, 2, 3]

全部匹配 → 返回 records.size()=4 ✓

为什么这个方法成立？数组升序，学号从 0 开始连续编号。如果没缺人，records = [0, 1, 2, ..., n-1]，每个位置records[i] == i。如果缺了某个人k，那么从位置k开始，后面的学号都比下标大 1：

• records = [0, 1, 2, 3, 5] → 缺了4，从位置4开始 records[i] = i+1

• records = [0, 1, 3, 4, 5] → 缺了2，从位置2开始 records[i] = i+1

所以第一个records[i] != i的下标i就是缺失值。

复杂度：时间 O(n)（最坏遍历整个数组），空间 O(1)

优缺点：

• 优点：代码简洁，空间 O(1)，利用了升序性质

• 缺点：时间 O(n)，没有利用升序性质做到 O(log n)

面试官会认可，但会追问"数组是有序的，能不能更快？" → 引出二分查找

解法三：位运算（异或 XOR）

思路：利用异或运算的两个性质：a ^ a = 0（相同数异或为 0）、a ^ 0 = a（任何数异或 0 为自身）。把"数组中所有元素"和"0 到 n 的所有完整学号"异或在一起，成对出现的会抵消为 0，最后剩下的就是缺失的那个数。

int takeAttendance(vector<int>& records) { int xorResult = 0; ​ // 把数组中所有学号异或进去 for (int r : records) { xorResult ^= r; } ​ // 把完整学号 0 到 n 异或进去（n = records.size()，因为缺了一个） for (int i = 0; i <= records.size(); i++) { xorResult ^= i; } ​ return xorResult; }

执行过程演示：

records = [0, 1, 2, 3, 5], n = 5（数组有5个元素，完整应有0~5共6个学号）

第1步: 异或数组中所有元素

0 ^ 1 ^ 2 ^ 3 ^ 5 = 0 ^ 1 = 1 → 1 ^ 2 = 3 → 3 ^ 3 = 0 → 0 ^ 5 = 5，xorResult = 5

第2步: 异或完整学号 0 ~ 5

5 ^ 0 = 5 → 5 ^ 1 = 4 → 4 ^ 2 = 6 → 6 ^ 3 = 5 → 5 ^ 4 = 1 → 1 ^ 5 = 4，xorResult = 4 ✓

为什么是 4？因为：(0^0) ^ (1^1) ^ (2^2) ^ (3^3) ^ 4 ^ (5^5) = 0 ^ 0 ^ 0 ^ 0 ^ 4 ^ 0 = 4

直觉理解：想象你有两组数字：

• 完整学号: [0, 1, 2, 3, 4, 5] ← 应该有的

• 实际到场: [0, 1, 2, 3, 5] ← 实际有的，缺了 4

把两组数字混在一起异或，成对的（0和0、1和1、...）全部抵消为 0，只剩下多出来的那个 4。

为什么循环到<= records.size()？数组有n个元素（缺了 1 个），所以完整学号应该是0到n，共n+1个。比如records = [0,1,2,3,5]有 5 个元素，完整应该是0~5共 6 个，缺的是 4。所以异或完整学号要循环到records.size()（即 5），包含 5。

复杂度：时间 O(n)（两次遍历），空间 O(1)

优缺点：

• 优点：空间 O(1)，不需要数组有序（即使数组打乱了也能用），思路巧妙

• 缺点：两次遍历，常数项比解法二大

能展示你对位运算的理解。面试官可能会问"异或的顺序重要吗？" → 不重要，异或满足交换律和结合律。

解法四：数学（高斯求和公式）

思路：如果一个人都不缺，学号 0 到 n 的总和是0 + 1 + 2 + ... + n = n(n+1)/2（高斯求和公式）。现在缺了一个人，实际总和 = 理论总和 - 缺失的学号。所以：缺失的学号 = 理论总和 - 实际总和

int takeAttendance(vector<int>& records) { int n = records.size(); // 数组有 n 个元素，完整应有 n+1 个学号(0~n) ​ // 理论总和: 0 + 1 + 2 + ... + n = n*(n+1)/2 int expectedSum = n * (n + 1) / 2; ​ // 实际总和 int actualSum = 0; for (int r : records) { actualSum += r; } ​ // 差值就是缺失的学号 return expectedSum - actualSum; }

执行过程演示：

records = [0, 1, 2, 3, 5], n = 5

第1步: 理论总和 expectedSum = 5 * 6 / 2 = 15（即 0+1+2+3+4+5 = 15）

第2步: 实际总和 actualSum = 0 + 1 + 2 + 3 + 5 = 11

第3步: 缺失学号 = 15 - 11 = 4 ✓

为什么 n = records.size()？数组有n个元素，意味着到场了n个人。因为缺了 1 个，所以总共有n+1个学号（0 到 n）。因此理论总和是0+1+...+n = n*(n+1)/2。

复杂度：时间 O(n)（遍历一次求和），空间 O(1)

优缺点：

• 优点：一次遍历，空间 O(1)，不需要数组有序（打乱了也能用），数学思路优雅

• 缺点：n*(n+1)/2可能溢出（当 n 很大时），需要用long long

溢出问题：当n = 10000时，n*(n+1)/2 = 50005000，int范围足够（约 21 亿）。但如果 n 更大，需要用long long：

long long expectedSum = (long long)n * (n + 1) / 2; long long actualSum = 0; for (int r : records) actualSum += r; return expectedSum - actualSum;

面试官最喜欢的解法之一。简洁、高效。可能会追问"如果缺失的不是一个而是两个呢？" → 高斯公式不再直接适用，需要其他方法。

四种解法对比总表

面试官: "怎么找缺失的学号？"

你: "我想到几种方法: 1. 最直觉的哈希表，但空间 O(n)；2. 利用有序直接遍历，看 records[i] != i，O(1) 空间；3. 不依赖有序的高斯求和，理论和减实际和，一次遍历 O(1) 空间；4. 同样不依赖有序的位运算异或，成对抵消。其中 2 利用有序做到了最简洁，如果要更快，数组有序可以用二分查找做到 O(log n)"

面试官: "那就写最优的"

二分查找（O(log n)）

策略:先给出多种解法展示思维广度，再写最优解展示深度。面试官不仅看你的代码，更看你分析问题的角度。