【算法通关指南：算法基础篇】二分算法：1.在排序树组中查找元素的第一个和最后一个位置 2.牛可乐和魔法封印
🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人方向学习者
❄️个人专栏：《算法通关指南》
✨ 永远相信美好的事情即将发生
文章目录
前言
本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长
一、二分算法
当我们的解具有二段性时，就可以使⽤二分算法找出答案：
• 根据待查找区间的中点位置，分析答案会出现在哪⼀侧；
• 接下来舍弃一半的待查找区间，转而在有答案的区间内继续使用二分算法查找结果。
时间复杂度为：O(logN)
STL中的二分查找 ：lower_bound ：大于等于x的最小元素，返回的是迭代器；时间复杂度：O(log N) 。upper_bound ：大于x的最小元素，返回的是迭代器。时间复杂度：O(log N) 。
二、在排序树组中查找元素的第一个和最后一个位置
2.1题目
2.2 算法原理
左右端点求法：
（1）定义两个指针指向数组的头和尾
（2）二分区间
（3）判断获取的端点值是否合法
二分容易死循环的环节
(1)区间缩小头尾指针的相遇条件
(2)中值得求法
2.3代码
class Solution{ public: vector<int>searchRange(vector<int>& nums, int target){if(nums.size()==0)return{-1,-1};//二分查找左端点 int left =0,right = nums.size()-1;while(left < right){ int mid =(left + right)/2;if(nums[mid]>= target) right = mid;else left = mid +1;}if(nums[left]!= target)return{-1,-1}; int retleft = left;//二分查找右端点 left =0,right = nums.size()-1;while(left < right){ int mid =(left + right +1)/2;if(nums[mid]<= target) left = mid;else right = mid -1;}return{retleft,right};}};三、牛可乐和魔法封印
3.1题目
链接：牛可乐和魔法封印
3.2 算法原理
二分查找算法模版题，依照第一题思路来写即可
注： 有可能并没有这个区间，需要在⼆分结束之后判断⼀下。
3.3代码
#include <iostream> using namespace std; const int N =1e5+10; typedef long long LL; LL a[N]; int n; int binary_search(int x,int y){ LL l =1,r = n;//查找左端点while(l < r){ LL mid =(l + r)/2;if(a[mid]>= x) r = mid;else l = mid +1;} LL retl = l;//判断端点是否合法if(a[l]< x)return0;//查找右端点 l =1,r = n;while(l < r){ LL mid =(l + r +1)/2;if(a[mid]<= y) l = mid;else r = mid -1;}if(a[r]> y)return0;return r - retl +1;} int main(){ cin >> n;for(int i =1;i <= n;i++) cin >> a[i]; int q; cin >> q;while(q--){ int x,y; cin >> x >> y; int ret =binary_search(x,y); cout << ret << endl;}return0;}总结与每日励志
✨本次围绕二分算法展开，讲解其二段性核心逻辑及STL二分函数，结合两道实战题实操演练，重点掌握左右端点查找的二分模版、mid取整技巧及端点合法性判断，规避死循环误区。算法学习重在沉淀，每一道模版题的练习，都是突破瓶颈的底气。✨ 永远相信美好的事情即将发生，坚持刷题、深耕细节，不慌不忙，稳步前行，终会在算法之路上，遇见更好的自己！
