【优选算法】(实战感悟二分查找算法的思想原理)

Ne0inhk

24 Mar 2026 — 30 min read

🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》《数据结构与算法》《C++知识内容》《Linux系统知识》《算法刷题指南》《测评文章活动推广》
✨逆境不吐心中苦,顺境不忘来时路!✨🎬 博主简介:

在算法的世界里,有一类算法看似简洁易懂,却能在海量数据中实现效率的飞跃,二分查找便是其中的典范.它作为优选算法家族中不可或缺的一员,以“分而治之”的核心思想,将线性查找的低效困境彻底打破,成为面试高频、工程常用的核心算法之一.二分查找的价值,远不止于"查找目标值"这一基础功能.它的核心魅力在于"高效收缩范围"的思想,将原本O(n)的线性时间复杂度优化至O(log n),这种效率的提升在数据量庞大时尤为显著——当数据规模达到100万时,线性查找最坏需遍历100万次,而二分查找仅需20次左右;当数据突破10亿,二分查找也只需30次就能锁定范围,这种量级的差距,正是优选算法的核心意义所在.更重要的是,二分查找的思想并非局限于单纯的查找场景,它还能延伸到最值求解、边界查找、旋转数组查找等复杂问题中,成为解决各类"二段性"问题的通用思路.本文将跳出"死记模板"的误区,结合实战中的亲身感悟,拆解二分查找的思想原理——从"二段性"这一核心本质出发,解读其分治思想的底层逻辑,剖析实战中常见的边界陷阱与避坑技巧,让读者不仅能看懂二分查找的代码,更能理解每一行逻辑背后的思考,真正将"分而治之"的思想内化为解决问题的能力.毕竟,算法的学习从来不是背诵代码,而是领悟其背后的思维方式,二分查找的实战之路,既是对细节的打磨,更是对高效解题思维的锤炼.废话不多说,下面跟着小编的节奏🎵一起去疯狂的学习吧!

1.二分查找算法背景介绍

1️⃣算法背景
二分查找(Binary Search),也叫折半查找,是一种针对有序数据集的高效查找算法,属于减治算法(将问题规模每次缩小一半)的经典应用.
在二分查找出现前,最基础的查找方式是顺序查找(线性查找):逐个遍历数据元素,直到找到目标值.

顺序查找时间复杂度为 O(n),数据量较小时尚可使用;
当数据量达到百万、千万级别时,顺序查找效率极低,无法满足快速检索需求.
二分查找正是为了解决大规模有序数据的高效查找问题而生,通过不断缩小查找范围,大幅降低查找次数.

2️⃣核心适用前提
二分查找并非所有场景都能用,必须满足3个关键条件:
1.数据序列有序(升序或降序排列);
2. 数据结构支持随机访问(如数组,链表因无法快速定位中间元素,不适合二分查找);
3. 数据为静态数据(无频繁插入/删除,否则会破坏有序性).

3️⃣核心原理
二分查找的核心思想:每次取查找区间的中间元素与目标值比较,将查找范围直接缩小一半,重复此过程直到找到目标或确认目标不存在.
简单理解:就像查字典,不会从头翻到尾,而是先翻中间页,根据页码大小判断目标字在左半还是右半,再继续折半查找.

算法流程
①定义 left,right 指针,分别指向数组的左右区间.
②找到待查找区间的中间点 mid,找到之后分三种情况讨论:
(1)arr[mid] == target 说明正好找到,返回 mid 的值;
(2)arr[mid] > target 说明 [mid, right] 这段区间都是大于 target 的,因此舍去右边区间,在左边 [left, mid - 1] 的区间继续查找,即让 right = mid - 1,然后重复2过程;
(3)arr[mid] < target 说明 [left, mid] 这段区间的值都是小于 target 的,因此舍去左边区间,在右边 [mid + 1, right] 区间继续查找,即让 left = mid + 1,然后重复 2 过程;
③当 left 与 right 错开时,说明整个区间都没有这个数,返回 -1.

核心代码

classSolution{public:intsearch(vector<int>&nums,int target){//初始化 left 与 right 指针int left =0, right = nums.size()-1;//由于两个指针相交时，当前元素还未判断，因此需要取等号while(left <= right){//先找到区间的中间元素int mid = left +(right - left)/2;//分三种情况讨论if(nums[mid]== target)return mid;elseif(nums[mid]> target) right = mid -1;else left = mid +1;}//如果程序⾛到这⾥，说明没有找到⽬标值，返回 -1return-1;}};

完整测试代码

#include<iostream>#include<vector>usingnamespace std;classSolution{public:intsearch(vector<int>&nums,int target){//初始化left与right指针int left =0, right = nums.size()-1;//由于两个指针相交时，当前元素还未判断，因此需要取等号while(left <= right){//先找到区间的中间元素（防溢出写法）int mid = left +(right - left)/2;//分三种情况讨论if(nums[mid]== target)return mid;elseif(nums[mid]> target) right = mid -1;else left = mid +1;}//如果程序⾛到这⾥，说明没有找到⽬标值，返回 -1return-1;}};intmain(){ Solution sol; vector<int> nums1 ={1,3,5,7,9};int target1 =5; cout <<"测试用例1：数组 [1,3,5,7,9]，查找 5"<< endl; cout <<"查找结果下标："<< sol.search(nums1, target1)<<"\n\n"; vector<int> nums2 ={2,4,6,8,10};int target2 =2; cout <<"测试用例2：数组 [2,4,6,8,10]，查找 2"<< endl; cout <<"查找结果下标："<< sol.search(nums2, target2)<<"\n\n"; vector<int> nums3 ={0,1,2,3,4};int target3 =4; cout <<"测试用例3：数组 [0,1,2,3,4]，查找 4"<< endl; cout <<"查找结果下标："<< sol.search(nums3, target3)<<"\n\n"; vector<int> nums4 ={10,20,30};int target4 =25; cout <<"测试用例4：数组 [10,20,30]，查找 25"<< endl; cout <<"查找结果下标："<< sol.search(nums4, target4)<<"\n\n"; vector<int> nums5 ={8};int target5 =8; cout <<"测试用例5：数组 [8]，查找 8"<< endl; cout <<"查找结果下标："<< sol.search(nums5, target5)<<"\n\n"; vector<int> nums6 ={8};int target6 =6; cout <<"测试用例6：数组 [8]，查找 6"<< endl; cout <<"查找结果下标："<< sol.search(nums6, target6)<< endl;return0;}

3.在排序数组中查找元素的第⼀个和最后⼀个位置(OJ题)

算法思路
用的还是二分思想,就是根据数据的性质,在某种判断条件下将区间一分为二,然后舍去其中一个区间,然后再另一个区间内查找;
方便叙述,用 x 表示该元素,resLeft 表示左边界,resRight 表示右边界.
寻找左边界思路:

寻找左边界:
- 我们注意到以左边界划分的两个区间的特点:
  - 左边区间 [left, resLeft - 1] 都是小于 x 的;
  - 右边区间（包括左边界）[resLeft, right] 都是大于等于 x 的;
- 因此,关于 mid 的落点，我们可以分为下面两种情况:
  - 当我们的 mid 落在 [left, resLeft - 1] 区间的时候,也就是 arr[mid] < target.说明 [left, mid] 都是可以舍去的,此时更新 left 到 mid + 1 的位置,继续在 [mid + 1, right] 上寻找左边界;
  - 当 mid 落在 [resLeft, right] 的区间的时候,也就是 arr[mid] >= target.说明 [mid + 1, right](因为 mid 可能是最终结果,不能舍去)是可以舍去的,此时更新 right 到 mid 的位置,继续在 [left, mid] 上寻找左边界;
由此,就可以通过二分,来快速寻找左边界;

注意: 这里找中间元素需要向下取整.
因为后续移动左右指针的时候:

左指针: left = mid + 1,是会向后移动的,因此区间是会缩小的;
右指针: right = mid,可能会原地踏步(比如: 如果向上取整的话,如果剩下1,2 两个元素,left == 1,right == 2,mid == 2.更新区间之后,left,right,mid 的值没有改变,就会陷入死循环).
因此一定要注意,当 right = mid 的时候,要向下取整.

寻找右边界思路:

寻右左边界:
- 用 resRight 表示右边界;
- 我们注意到右边界的特点:
  - 左边区间(包括右边界)[left, resRight] 都是小于等于 x 的;
  - 右边区间 [resRight+ 1, right] 都是大于 x 的;
- 因此,关于 mid 的落点,我们可以分为下面两种情况:
  - 当我们的 mid 落在 [left, resRight] 区间的时候,说明 [left, mid - 1](mid 不可以舍去,因为有可能是最终结果)都是可以舍去的,此时更新 left 到 mid 的位置
  - 当 mid 落在 [resRight+ 1, right] 的区间的时候,说明 [mid, right] 内的元素是可以舍去的,此时更新 right 到 mid - 1 的位置;
由此,就可以通过二分,来快速寻找右边界;

注意: 这里找中间元素需要向上取整。
因为后续移动左右指针的时候:

左指针: left = mid,可能会原地踏步(比如: 如果向下取整的话,如果剩下 1,2 两个元素,left == 1,right == 2,mid == 1.更新区间之后,left,right,mid 的值没有改变,就会陷入死循环).
右指针: right = mid - 1，是会向前移动的，因此区间是会缩小的;
因此一定要注意,当 right = mid 的时候,要向下取整.

二分查找算法总结:
请大家一定不要觉得背下模板就能解决所有二分问题.二分问题最重要的就是要分析题意,然后确定要搜索的区间,根据分析问题来写出二分查找算法的代码.要分析题意,确定搜索区间,不要死记模板,不要看左闭右开什么乱七八糟的题解.

模板记忆技巧:
1.关于什么时候用三段式,还是二段式中的某一个,一定不要强行去用,而是通过具体的问题分析情况,根据查找区间的变化确定指针的转移过程,从而选择一个模板.
2.当选择两段式的模板时:
在求mid的时候,只有 right - 1 的情况下,才会向上取整(也就是 +1 取中间数)

核心代码

classSolution{public: vector<int>searchRange(vector<int>& nums,int target){//处理边界情况if(nums.size()==0)return{-1,-1};int begin =0;//1. ⼆分左端点int left =0, right = nums.size()-1;while(left < right){int mid = left +(right - left)/2;if(nums[mid]< target) left = mid +1;else right = mid;}//判断是否有结果if(nums[left]!= target)return{-1,-1};else begin = left;//标记⼀下左端点//2. ⼆分右端点 left =0, right = nums.size()-1;while(left < right){int mid = left +(right - left +1)/2;if(nums[mid]<= target) left = mid;else right = mid -1;}return{begin, right};}};

完整测试代码

#include<iostream>#include<vector>usingnamespace std;classSolution{public: vector<int>searchRange(vector<int>& nums,int target){//处理边界情况if(nums.size()==0)return{-1,-1};int begin =0;//1.⼆分左端点int left =0, right = nums.size()-1;while(left < right){int mid = left +(right - left)/2;if(nums[mid]< target) left = mid +1;else right = mid;}//判断是否有结果if(nums[left]!= target)return{-1,-1};else begin = left;//标记⼀下左端点//2.⼆分右端点 left =0, right = nums.size()-1;while(left < right){int mid = left +(right - left +1)/2;if(nums[mid]<= target) left = mid;else right = mid -1;}return{begin, right};}};intmain(){ Solution sol; vector<int> nums1 ={};int target1 =0; vector<int> res1 = sol.searchRange(nums1, target1); cout <<"测试用例1：空数组，查找 0"<< endl; cout <<"结果：["<< res1[0]<<","<< res1[1]<<"]"<<"\n\n"; vector<int> nums2 ={5};int target2 =5; vector<int> res2 = sol.searchRange(nums2, target2); cout <<"测试用例2：数组 [5]，查找 5"<< endl; cout <<"结果：["<< res2[0]<<","<< res2[1]<<"]"<<"\n\n"; vector<int> nums3 ={5};int target3 =3; vector<int> res3 = sol.searchRange(nums3, target3); cout <<"测试用例3：数组 [5]，查找 3"<< endl; cout <<"结果：["<< res3[0]<<","<< res3[1]<<"]"<<"\n\n"; vector<int> nums4 ={5,7,7,8,8,10};int target4 =8; vector<int> res4 = sol.searchRange(nums4, target4); cout <<"测试用例4：数组 [5,7,7,8,8,10]，查找 8"<< endl; cout <<"结果：["<< res4[0]<<","<< res4[1]<<"]"<<"\n\n"; vector<int> nums5 ={2,2,2,3,4};int target5 =2; vector<int> res5 = sol.searchRange(nums5, target5); cout <<"测试用例5：数组 [2,2,2,3,4]，查找 2"<< endl; cout <<"结果：["<< res5[0]<<","<< res5[1]<<"]"<<"\n\n"; vector<int> nums6 ={1,3,5,7,7,7};int target6 =7; vector<int> res6 = sol.searchRange(nums6, target6); cout <<"测试用例6：数组 [1,3,5,7,7,7]，查找 7"<< endl; cout <<"结果：["<< res6[0]<<","<< res6[1]<<"]"<<"\n\n"; vector<int> nums7 ={5,7,7,8,8,10};int target7 =6; vector<int> res7 = sol.searchRange(nums7, target7); cout <<"测试用例7：数组 [5,7,7,8,8,10]，查找 6"<< endl; cout <<"结果：["<< res7[0]<<","<< res7[1]<<"]"<<"\n\n"; vector<int> nums8 ={1,2,3,4,5};int target8 =3; vector<int> res8 = sol.searchRange(nums8, target8); cout <<"测试用例8：数组 [1,2,3,4,5]，查找 3"<< endl; cout <<"结果：["<< res8[0]<<","<< res8[1]<<"]"<< endl;return0;}

4.x的平方根(OJ题)

算法思路:解法一(暴力查找)
依次枚举 [0, x] 之间的所有数 i:
(这里没有必要研究是否枚举到 x / 2 还是 x / 2 + 1.因为我们找到结果之后直接就返回了,往后的情况就不会再判断.反而研究枚举区间,既耽误时间,又可能出错)

如果 i * i == x,直接返回 x;
如果 i * i > x,说明之前的一个数是结果,返回 i - 1.

由于 i * i 可能超过 int 的最大值,因此使用 long long 类型.

核心代码

classSolution{public:intmySqrt(int x){//由于两个较⼤的数相乘可能会超过 int 最⼤范围//因此⽤ long longlonglong i =0;for(i =0; i <= x; i++){//如果两个数相乘正好等于 x，直接返回 iif(i * i == x)return i;//如果第⼀次出现两个数相乘⼤于 x，说明结果是前⼀个数if(i * i > x)return i -1;}//为了处理oj题需要控制所有路径都有返回值return-1;}};

算法思路:解法二(二分查找算法)
设 x 的平方根的最终结果为 index:
分析 index 左右两次数据的特点:

[0, index] 之间的元素,平方之后都是小于等于 x 的;
[index + 1, x] 之间的元素,平方之后都是大于 x 的.

因此可以使用二分查找算法.

核心代码

classSolution{public:intmySqrt(int x){if(x <1)return0;//处理边界情况int left =1, right = x;while(left < right){longlong mid = left +(right - left +1)/2;//防溢出if(mid * mid <= x) left = mid;else right = mid -1;}return left;}};

完整测试代码

#include<iostream>usingnamespace std;classSolution{public:intmySqrt(int x){if(x <1)return0;//处理边界情况int left =1, right = x;while(left < right){//mid 用long long防止平方后溢出longlong mid = left +(right - left +1)/2;//向上取整，防死循环if(mid * mid <= x) left = mid;else right = mid -1;}return left;}};intmain(){ Solution sol; cout <<"测试用例1：x = 0，平方根 = "<< sol.mySqrt(0)<< endl; cout <<"测试用例2：x = 1，平方根 = "<< sol.mySqrt(1)<< endl; cout <<"测试用例3：x = 2，平方根 = "<< sol.mySqrt(2)<< endl; cout <<"测试用例4：x = 4，平方根 = "<< sol.mySqrt(4)<< endl; cout <<"测试用例5：x = 8，平方根 = "<< sol.mySqrt(8)<< endl; cout <<"测试用例6：x = 9，平方根 = "<< sol.mySqrt(9)<< endl; cout <<"测试用例7：x = 16，平方根 = "<< sol.mySqrt(16)<< endl; cout <<"测试用例8：x = 2147483647，平方根 = "<< sol.mySqrt(2147483647)<< endl;return0;}

5.搜索插入位置(OJ题)

算法思路:解法(二分查找算法)
①分析插入位置左右两侧区间上元素的特点:
设插入位置的坐标为 index,根据插入位置的特点可以知道:

[left, index - 1] 内的所有元素均是小于 target 的;
[index, right] 内的所有元素均是大于等于 target 的.

②设 left 为本轮查询的左边界,right 为本轮查询的右边界.根据 mid 位置元素的信息,分析下一轮查询的区间:

当 nums[mid] >= target 时,说明 mid 落在了 [index, right] 区间上,mid 左边包括 mid 本身,可能是最终结果,所以我们接下来查找的区间在 [left, mid] 上.因此,更新 right 到 mid 位置,继续查找.
当 nums[mid] < target 时,说明 mid 落在了 [left, index - 1] 区间上,mid 右边但不包括 mid 本身,可能是最终结果,所以我们接下来查找的区间在 [mid + 1, right] 上.因此,更新 left 到 mid + 1 的位置,继续查找.

③直到我们的查找区间的长度变为1,也就是 left == right 的时候,left 或者 right 所在的位置就是我们要找的结果.

核心代码

classSolution{public:intsearchInsert(vector<int>& nums,int target){int left =0, right = nums.size()-1;while(left < right){int mid = left +(right - left)/2;if(nums[mid]< target) left = mid +1;else right = mid;}if(nums[left]< target)return right +1;return right;}};

完整测试代码

#include<iostream>#include<vector>usingnamespace std;classSolution{public:intsearchInsert(vector<int>& nums,int target){if(nums.empty())return0;int left =0, right = nums.size()-1;while(left < right){int mid = left +(right - left)/2;if(nums[mid]< target) left = mid +1;else right = mid;}if(nums[left]< target)return right +1;return right;}};intmain(){ Solution sol; vector<int> nums1; cout <<"1. 空数组，插入 5 → 位置："<< sol.searchInsert(nums1,5)<< endl; vector<int> nums2 ={1,3,5,6}; cout <<"2. [1,3,5,6] 查找 5 → 位置："<< sol.searchInsert(nums2,5)<< endl; cout <<"3. [1,3,5,6] 插入 2 → 位置："<< sol.searchInsert(nums2,2)<< endl; cout <<"4. [1,3,5,6] 插入 7 → 位置："<< sol.searchInsert(nums2,7)<< endl; cout <<"5. [1,3,5,6] 插入 0 → 位置："<< sol.searchInsert(nums2,0)<< endl; vector<int> nums3 ={8}; cout <<"6. [8] 查找 8 → 位置："<< sol.searchInsert(nums3,8)<< endl; cout <<"7. [8] 插入 10 → 位置："<< sol.searchInsert(nums3,10)<< endl;return0;}

6.山脉数组的峰顶索引(OJ题)

算法思路:解法一(暴力查找)
峰顶的特点:比两侧的元素都要大.
因此,我们可以遍历数组内的每一个元素,找到某一个元素比两边的元素大即可.
核心代码

classSolution{public:intpeakIndexInMountainArray(vector<int>& arr){int n = arr.size();//遍历数组内每⼀个元素，直到找到峰顶for(int i =1; i < n -1; i++)//峰顶满⾜的条件if(arr[i]> arr[i -1]&& arr[i]> arr[i +1])return i;//为了处理 oj 需要控制所有路径都有返回值return-1;}};

算法思路:解法二(二分查找)
1.分析峰顶位置的数据特点,以及山峰两旁的数据的特点:

峰顶数据特点:arr[i] > arr[i - 1] && arr[i] > arr[i + 1];
峰顶左边的数据特点:arr[i] > arr[i - 1] && arr[i] < arr[i + 1],也就是呈现上升趋势;
峰顶右边数据的特点:arr[i] < arr[i - 1] && arr[i] > arr[i + 1],也就是呈现下降趋势.

2.因此,根据 mid 位置的信息,我们可以分为下面三种情况:

如果 mid 位置呈现上升趋势,说明我们接下来要在 [mid + 1, right] 区间继续搜索;
如果 mid 位置呈现下降趋势,说明我们接下来要在 [left, mid - 1] 区间搜索;
如果 mid 位置就是山峰,直接返回结果.

核心代码

classSolution{public:intpeakIndexInMountainArray(vector<int>& arr){int left =1, right = arr.size()-2;while(left < right){int mid = left +(right - left +1)/2;if(arr[mid]> arr[mid -1]) left = mid;else right = mid -1;}return left;}};

完整测试代码

#include<iostream>#include<vector>usingnamespace std;classSolution{public:intpeakIndexInMountainArray(vector<int>& arr){int left =1, right = arr.size()-2;while(left < right){int mid = left +(right - left +1)/2;if(arr[mid]> arr[mid -1]) left = mid;else right = mid -1;}return left;}};intmain(){ Solution sol; vector<int> arr1 ={0,1,0}; cout <<"测试用例1：数组 [0,1,0]"<< endl; cout <<"峰值索引："<< sol.peakIndexInMountainArray(arr1)<<"\n\n"; vector<int> arr2 ={0,2,1,0}; cout <<"测试用例2：数组 [0,2,1,0]"<< endl; cout <<"峰值索引："<< sol.peakIndexInMountainArray(arr2)<<"\n\n"; vector<int> arr3 ={0,10,5,2}; cout <<"测试用例3：数组 [0,10,5,2]"<< endl; cout <<"峰值索引："<< sol.peakIndexInMountainArray(arr3)<<"\n\n"; vector<int> arr4 ={1,3,5,7,6,4,2}; cout <<"测试用例4：数组 [1,3,5,7,6,4,2]"<< endl; cout <<"峰值索引："<< sol.peakIndexInMountainArray(arr4)<<"\n\n"; vector<int> arr5 ={3,4,5,1}; cout <<"测试用例5：数组 [3,4,5,1]"<< endl; cout <<"峰值索引："<< sol.peakIndexInMountainArray(arr5)<< endl;return0;}

7.寻找峰值(OJ题)

算法思路:解法(二分查找算法)
寻找二段性：
任取一个点 i,与下一个点 i + 1,会有如下两种情况:

arr[i] > arr[i + 1]:此时左侧区域一定会存在山峰(因为最左侧是负无穷),那么我们可以去左侧去寻找结果;
arr[i] < arr[i + 1]:此时右侧区域一定会存在山峰(因为最右侧是负无穷),那么我们可以去右侧去寻找结果.
当我们找到二段性的时候,就可以尝试用二分查找算法来解决问题.

核心代码

classSolution{public:intfindPeakElement(vector<int>& nums){int left =0, right = nums.size()-1;while(left < right){// 关键：向上取整，避免区间只剩2个元素时死循环int mid = left +(right - left )/2;if(nums[mid]> nums[mid +1]){// 下降趋势：峰值在[left, mid]，收缩右边界 right = mid;}else{// 上升趋势：峰值在[mid+1, right]，收缩左边界 left = mid +1;}}// 循环结束left==right，即为峰值索引return left;}};

完整测试代码

#include<iostream>#include<vector>usingnamespace std;classSolution{public:intfindPeakElement(vector<int>& nums){int left =0, right = nums.size()-1;while(left < right){// 关键：向上取整，避免区间只剩2个元素时死循环int mid = left +(right - left )/2;if(nums[mid]> nums[mid +1]){// 下降趋势：峰值在[left, mid]，收缩右边界 right = mid;}else{// 上升趋势：峰值在[mid+1, right]，收缩左边界 left = mid +1;}}// 循环结束left==right，即为峰值索引return left;}};intmain(){ Solution sol; vector<int> nums1 ={1,2,3,1}; cout <<"测试用例1：数组 [1,2,3,1]"<< endl; cout <<"峰值索引："<< sol.findPeakElement(nums1)<<"\n\n"; vector<int> nums2 ={1,2,1,3,5,6,4}; cout <<"测试用例2：数组 [1,2,1,3,5,6,4]"<< endl; cout <<"峰值索引："<< sol.findPeakElement(nums2)<<"\n\n"; vector<int> nums3 ={5}; cout <<"测试用例3：数组 [5]"<< endl; cout <<"峰值索引："<< sol.findPeakElement(nums3)<<"\n\n"; vector<int> nums4 ={1,2,3,4}; cout <<"测试用例4：数组 [1,2,3,4]"<< endl; cout <<"峰值索引："<< sol.findPeakElement(nums4)<<"\n\n"; vector<int> nums5 ={4,3,2,1}; cout <<"测试用例5：数组 [4,3,2,1]"<< endl; cout <<"峰值索引："<< sol.findPeakElement(nums5)<<"\n\n"; vector<int> nums6 ={0,1}; cout <<"测试用例6：数组 [0,1]"<< endl; cout <<"峰值索引："<< sol.findPeakElement(nums6)<< endl;return0;}

8.寻找旋转排序数组中的最小值(OJ题)

关于暴⼒查找,只需遍历⼀遍数组,这⾥不再赘述.
算法思路:解法(⼆分查找)
题⽬中的数组规则如下图所示:

其中 C 点就是我们要求的点。
二分的本质:找到一个判断标准,使得查找区间能够一分为二.
通过图像我们可以发现,[A，B] 区间内的点都是严格大于 D 点的值的,C 点的值是严格小于 D 点的值的.但是当 [C，D] 区间只有一个元素的时候,C 点的值是可能等于 D 点的值的.
因此,初始化左右两个指针 left，right:
然后根据 mid 的落点,我们可以这样划分下一次查询的区间:

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

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

核心代码

classSolution{public:intfindMin(vector<int>& nums){int left =0, right = nums.size()-1;int x = nums[right];//标记⼀下最后⼀个位置的值while(left < right){int mid = left +(right - left)/2;if(nums[mid]> x) left = mid +1;else right = mid;}return nums[left];}};

完整测试代码

#include<iostream>#include<vector>usingnamespace std;classSolution{public:intfindMin(vector<int>& nums){int left =0, right = nums.size()-1;int x = nums[right];//标记⼀下最后⼀个位置的值while(left < right){int mid = left +(right - left)/2;if(nums[mid]> x) left = mid +1;else right = mid;}return nums[left];}};intmain(){ Solution sol; vector<int> nums1 ={3,4,5,1,2}; cout <<"测试用例1：[3,4,5,1,2] → 最小值："<< sol.findMin(nums1)<<"\n\n"; vector<int> nums2 ={4,5,6,7,0,1,2}; cout <<"测试用例2：[4,5,6,7,0,1,2] → 最小值："<< sol.findMin(nums2)<<"\n\n"; vector<int> nums3 ={1,2,3,4,5}; cout <<"测试用例3：[1,2,3,4,5] → 最小值："<< sol.findMin(nums3)<<"\n\n"; vector<int> nums4 ={1}; cout <<"测试用例4：[1] → 最小值："<< sol.findMin(nums4)<<"\n\n"; vector<int> nums5 ={2,1}; cout <<"测试用例5：[2,1] → 最小值："<< sol.findMin(nums5)<<"\n\n"; vector<int> nums6 ={1,2}; cout <<"测试用例6：[1,2] → 最小值："<< sol.findMin(nums6)<< endl;return0;}

9.点名(OJ题)

算法思路:解法(二分查找算法)
关于这道题中,时间复杂度为 O(N) 的解法有很多种,而且也是比较好想的,这里就不再赘述.
本题只讲解一个最优的二分法,来解决这个问题.
在这个升序的数组中，我们发现:

在第一个缺失位置的左边,数组内的元素都是与数组的下标相等的;
在第一个缺失位置的右边,数组内的元素与数组下标是不相等的.

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

核心代码

classSolution{public:inttakeAttendance(vector<int>& records){int left =0, right = records.size()-1;while(left < right){int mid = left +(right - left)/2;// 避免溢出if(records[mid]== mid){// 前半部分无缺失，向右查找 left = mid +1;}else{// 缺失在左半部分（包含mid），向左收缩 right = mid;}}// 边界判断：若最后一个位置仍满足records[left]==left，说明缺失的是最后一个学号（records.size()）return records[left]== left ? records.size(): left;}};

完整测试代码

#include<iostream>#include<vector>usingnamespace std;classSolution{public:inttakeAttendance(vector<int>& records){int left =0, right = records.size()-1;while(left < right){int mid = left +(right - left)/2;//避免溢出if(records[mid]== mid){//前半部分无缺失，向右查找 left = mid +1;}else{//缺失在左半部分（包含mid），向左收缩 right = mid;}}//边界判断：若最后一个位置仍满足records[left]==left，说明缺失的是最后一个学号（records.size()）return records[left]== left ? records.size(): left;}};intmain(){ Solution sol; vector<int> rec1 ={0,1,2,3,5}; cout <<"测试用例1：[0,1,2,3,5] → 缺席学号："<< sol.takeAttendance(rec1)<< endl; vector<int> rec2 ={0,1,2,3,4,5,6,8}; cout <<"测试用例2：[0,1,2,3,4,5,6,8] → 缺席学号："<< sol.takeAttendance(rec2)<< endl; vector<int> rec3 ={0}; cout <<"测试用例3：[0] → 缺席学号："<< sol.takeAttendance(rec3)<< endl; vector<int> rec4 ={1}; cout <<"测试用例4：[1] → 缺席学号："<< sol.takeAttendance(rec4)<< endl; vector<int> rec5 ={0,1,2}; cout <<"测试用例5：[0,1,2] → 缺席学号："<< sol.takeAttendance(rec5)<< endl; vector<int> rec6 ={0,2}; cout <<"测试用例6：[0,2] → 缺席学号："<< sol.takeAttendance(rec6)<< endl;return0;}

🚀真正的勇者不是流泪的人,而是含泪奔跑的人!

敬请期待下一篇文章内容:【优选算法】(实战领略前缀和的真谛)

每日心灵鸡汤:不要因为小事闷闷不乐!
烦躁的时候就尽量少说话,也不要做任何决定,安静的待会,你已经长大了,一些难过的情绪,要学会自己消化,不为难自己,别自我折磨、自我消耗.有人握紧你的手就可能会松开,有人给你承诺就有失望,心
情不好就听歌,饿了就吃饭,怕黑就一直开灯睡觉,把期待降低,把依赖变少,努力把生活过成自己想要
的样子.希望你做什么就去做,做自由的风,做纯粹的火,做缥缈的云,希望你不被世俗缠绕,不被谣言淹没,希望你做自己,随心所欲,总之去做炽热的光吧,太阳也好,月亮也罢,做最炽热,做最闪耀最像你的你.