信阳市网站建设_网站建设公司_C#_seo优化

算法场景

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

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

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;}

总结

这两道题虽然背景不同，但本质高度相似：

• 都是二分查找的变形

• 核心在于：

  • 找到单调性
  • 明确判断条件
  • 缩小区间直到答案唯一

📌 常见二分套路总结：

• 旋转数组：与nums[right]比较
• 缺失数字：比较nums[mid]与mid

只要抓住“哪一侧一定有答案”，二分查找就会变得非常自然。

✨ 坚持用清晰易懂的图解+代码语言， 让每个知识点都简单直观！
🚀个人主页：不呆头 · CSDN
🌱代码仓库：不呆头 · Gitee
📌专栏系列：

• 📖 《C语言》
• 🧩 《数据结构》
• 💡 《C++》
• 🐧 《Linux》

💬座右铭：“不患无位，患所以立。”