【算法通关指南：算法基础篇】二分算法：1.在排序树组中查找元素的第一个和最后一个位置 2.牛可乐和魔法封印

🔥小龙报：个人主页 🎬作者简介：C++研发，嵌入式，机器人方向学习者 ❄️个人专栏：《算法通关指南》 ✨ 永远相信美好的事情即将发生

文章目录

• 前言
• 一、二分算法
• 二、在排序树组中查找元素的第一个和最后一个位置
• • 2.1题目
  • • 2.2 算法原理
    • 2.3代码
• 三、牛可乐和魔法封印
• • 3.1题目
  • • 3.2 算法原理
    • 3.3代码
• 总结与每日励志

前言

本专栏聚焦算法题实战，系统讲解算法模块：以《c++编程》，《数据结构和算法》《基础算法》《算法实战》 等几个板块以题带点，讲解思路与代码实现，帮助大家快速提升代码能力ps:本章节题目分两部分，比较基础笔者只附上代码供大家参考，其他的笔者会附上自己的思考和讲解，希望和大家一起努力见证自己的算法成长

一、二分算法

当我们的解具有二段性时，就可以使⽤二分算法找出答案： • 根据待查找区间的中点位置，分析答案会出现在哪⼀侧； • 接下来舍弃一半的待查找区间，转而在有答案的区间内继续使用二分算法查找结果。 时间复杂度为：O(logN)

STL中的二分查找 ：

二、在排序树组中查找元素的第一个和最后一个位置

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)
return 0;

//查找右端点
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)
return 0;
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;
}

return 0;
}

总结与每日励志

✨本次围绕二分算法展开，讲解其二段性核心逻辑及STL二分函数，结合两道实战题实操演练，重点掌握左右端点查找的二分模版、mid取整技巧及端点合法性判断，规避死循环误区。算法学习重在沉淀，每一道模版题的练习，都是突破瓶颈的底气。✨ 永远相信美好的事情即将发生，坚持刷题、深耕细节，不慌不忙，稳步前行，终会在算法之路上，遇见更好的自己！