【LeetCode 153 173_二分查找】寻找旋转排序数组中的最小值缺失的数字-平芜编程栈

算法场景

当题目中存在有序性或单调性时，就应优先考虑二分查找：例如数组整体有序或局部有序（如旋转数组）、某个条件在区间内呈现“前真后假”或“前假后真”的分界特征、下标与数值存在固定关系（如缺失数字问题），或答案位于一个连续区间且可通过判断函数验证可行性；只要能够通过一次判断就排除一半区间，并且数据规模较大、要求O ( l o g n ) O(logn)O(logn)复杂度，二分查找就是最合适的解法。

算法场景
- 一、寻找旋转排序数组中的最小值
- - 1.1 题目链接
  - 1.2 题目描述
  - 1.3 题目示例
  - 1.4 算法思路
  - - 核心观察
    - 判断逻辑
  - 1.5 核心代码
  - 1.6 示例测试（总代码）
- 二、缺失的数字（剑指 Offer）
- - 2.1 题目链接
  - 2.2 题目描述
  - 2.3 题目示例
  - 2.4 算法思路
  - - 核心规律
    - 二分判断
  - 2.5 核心代码
  - 2.6 示例测试（总代码）
总结

一、寻找旋转排序数组中的最小值

1.1 题目链接

LeetCode153_寻找旋转排序数组中的最小值【点击进入】

1.2 题目描述

给你一个不含重复元素的整数数组nums，它原本是一个升序排列的数组，但在某个未知的点上进行了旋转。

请你找出并返回数组中的最小元素。

要求时间复杂度为O(log n)。

1.3 题目示例

输入：nums = [4,5,6,7,0,1,2] 输出：0

输入：nums = [3,4,5,1,2] 输出：1

1.4 算法思路

这是一个典型的二分查找变形题。

核心观察

旋转后的数组可以看成两段递增数组
最小值一定是旋转点
我们可以将nums[right]作为比较基准

判断逻辑

若nums[mid] > nums[right]
👉 说明最小值一定在mid 的右侧
否则
👉 最小值在mid 或 mid 的左侧

通过不断缩小区间，最终left == right时，即为最小值下标。

1.5 核心代码

classSolution{public:intfindMin(vector<int>&nums){intleft=0;intright=nums.size()-1;intx=nums[right];while(left<right){intmid=left+(right-left)/2;if(nums[mid]>x)left=mid+1;elseright=mid;}returnnums[left];}};

1.6 示例测试（总代码）

#include<bits/stdc++.h>usingnamespacestd;classSolution{public:intfindMin(vector<int>&nums){intleft=0;intright=nums.size()-1;intx=nums[right];while(left<right){intmid=left+(right-left)/2;if(nums[mid]>x)left=mid+1;elseright=mid;}returnnums[left];}};intmain(){Solution s;vector<int>nums={4,5,6,7,0,1,2};cout<<s.findMin(nums)<<endl;return0;}

二、缺失的数字（剑指 Offer）

2.1 题目链接

LeetCode173_缺失的数字【点击进入】

2.2 题目描述

一个长度为n-1的递增数组records，所有数字都在[0, n-1]范围内，且不重复。

数组中恰好缺失一个数字，请找出这个缺失的数字。

2.3 题目示例

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

输入：records = [0,1,2,3] 输出：4

2.4 算法思路

这是一个非常经典的“下标和值关系” 二分查找题。

核心规律

在理想情况下：records[i] == i
一旦出现缺失数字：
- 缺失数字左侧：records[i] == i
- 缺失数字右侧：records[i] > i

二分判断

若records[mid] == mid
👉 缺失数字在右侧
否则
👉 缺失数字在左侧（包括 mid）

最终left即为缺失的数字。

2.5 核心代码

classSolution{public:inttakeAttendance(vector<int>&records){intleft=0;intright=records.size()-1;while(left<right){intmid=left+(right-left)/2;if(records[mid]==mid)left=mid+1;elseright=mid;}returnleft==records[left]?left+1:left;}};

2.6 示例测试（总代码）

#include<bits/stdc++.h>usingnamespacestd;classSolution{public:inttakeAttendance(vector<int>&records){intleft=0;intright=records.size()-1;while(left<right){intmid=left+(right-left)/2;if(records[mid]==mid)left=mid+1;elseright=mid;}returnleft==records[left]?left+1:left;}};intmain(){Solution s;vector<int>records={0,1,2,3,4,6,7};cout<<s.takeAttendance(records)<<endl;return0;}