SCS_user_EHQ0z2l6el查看:6 回复:7 评论:6 创建时间:2023-10-21T23:12:12用户:SCS_user_EHQ0z2l6el查看:6 回复:7 评论:6 创建时间:2023-10-21T23:12:12
号回来了，所以接着接
这次讲分治）
分治
首先要理解什么是分治
古语有云：话说天下大势，分久必合，合久必分
当然和分治没半毛钱关系
通俗点说是分而治之
我们将一个大问题通过例如划分数据规模的方式变成很多个相似小问题来解决，
然后再将全部解决的小问题合并从而解决一个大问题
有点大学的微积分的思想）
简单来讲就是把大大滴问题分成一个一个一个（*114）小问题
某些题目可以直接采用这种方式来降低数据规模（OI人狂喜）
一般题目会涉及的比较常见的分治算法，例如有快速排序，归并排序
还有比较经典的，最经常考察的分治算法就是二分。包括二分查找以及二分答案。
二分查找：一定要明确2个条件：1.数字有序2.存储结构支持随机访问。
比如说
在长度为10的有序数组里面查找一个元素看他在不在，
另外有序的意思是指数是从大到小或者从小到大排序的
数组{1,2,4,6,10,15,16,19,21,22}
找到数16在哪个地方
一般人会想”从头到尾遍历一遍不就行了“
这样的时间复杂度是O(N);
那如果数组范围是114514要查询1919810次呢？
（有学过哈希的先别急）
那这就要用到我们的二分查找了
二分查找
我们先来玩个游戏
你从1～9随便想个数，我来猜，然后根据描述来看下一条
1：是5吗？大了（看2） /小了（看6） /对了
2：是3吗？大了（看3） / 小了（看5） /对了
3：是2吗？大了（看4） / 小了（不可能） /对了
4：是1吗？大了（不可能）/小了（也不可能）/对了
5：是4吗？大了（不可能）/小了（也不可能）/对了
6：是7吗？大了（看7） /小了（看8） /对了
7：是6吗？大了（不可能）/ 小了（也不可能）/对了
8：是8吗？大了（不可能）/ 小了（看9） /对了
9：是9吗？大了（不可能）/小了（也不可能）/对了
基本上你按着步骤来4步之内就能猜中；
这就利用到了二分法
每次我猜都是按照（l+r）/2来猜的
一开始l是1，r是9
也就是数的下限和上限
然后，我取他们的平均数（向下取整）也就是对半分来猜
如果大了，那么上限就变为刚才的平均数
如果小了，那么下限就变为刚才的平均数
如此反复取平均减少上限下限差距
最后就会得到结果
而二分查找也差不多是一个道理
给你个有序数组让你找元素
那就可以像刚才那样对半分来二分查找
注意，二分查找的前提是有序
没序数组还是一个一个找吧（实在不行排序然后二分也可以）
二分答案下次找一道题来讲吧（主要是懒）
好了，有分治以及二分查找的内容我就讲到这里了
感兴趣的朋友可以去翻我之前的教学帖
也可以翻翻评论区看我有没有写代码）（写二分查找的代码）
再见awa
SCS_user_EHQ0z2l6el
#include<iostream>
using namespace std;
int cha[10001],n;//数组、数据范围
int find(int a){//查找返回数组下标，没有则返回-1
int l=0,r=n-1;
while(r>l){
int min=(l-r)/2+r;
//int min=(l+r)/2; 可能会溢出
if(cha[min]<a){//二分
l=min;
}else if(cha[min]==a){
return min;
}else{
r=min-1;
}
}
if(cha[l]!=a)return -1;
return l;
}
int main(){
cin>>n;
for(int i=0;i<n;i++)//输入
cin>>cha[i];
int x;
cin>>x;//询问次数
for(int i=0;i<x;i++){
int l;
cin>>l;
cout<<find(l)+1<<endl;;
}
}点赞0
评论
黏贴著名大佬的话
I'm just in a mood to sh*tpost. Don't take it too seriously.
Things that I have heard of, but don't know (imagine how many things I haven't even heard of):
If you know at least 3 of these things and you are not red — you are doing it wrong. Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
点赞0
评论
