网站要设置哪些栏目,铁岭做网站信息,wordpress 分析,苏州中设建设集团有限公司网站大家好#xff0c;今天进入一个实用算法#xff1a;分治算法。 1.分治算法介绍
分治算法#xff0c;大概就是将一个大问题拆解成若干个小问题#xff0c;将小问题一一解决#xff0c;大问题也就迎刃而解。它包含了多种算法#xff0c;比如递归、递推等。这里就讲解一下其…大家好今天进入一个实用算法分治算法。 1.分治算法介绍
分治算法大概就是将一个大问题拆解成若干个小问题将小问题一一解决大问题也就迎刃而解。它包含了多种算法比如递归、递推等。这里就讲解一下其中比较经典的一个算法二分查找算法。 2.二分查找算法介绍
二分查找算法适用范围、优点
二分查找算法适用于在有序数组中寻找某个数其时间复杂度较正常的顺序查找而言大大减小从On的效率提高到了Olog n。
如要在100个数中查询一个数在最坏的情况下顺序查找需要循环100次而二分查找只需要循环不到10次。
二分查找算法基本思想
1.定点
先确定数组中间的数在确定查找范围的左端点 l 右端点 r 。
2.跳出条件
若左端点 l 与右端点 r 靠在了一起再做判断如果 a[l] t 查找的数就在 l 位置如果a[r] t 查找的数就在 r 位置两者都不是说明数组 a 中没有要查询的数 t 。
3.进一步查询
若要查询的数 t 小于等于中间的数 a[mid] 则右端点 r mid ,否则左端点 l mid1 然后接着进行步骤1和步骤2. 3.二分查找算法代码
题目
现给定一个长度为 n 的有序数组 a 有 m 次询问每次询问都输入一个数 t 若数组 a 中有 t 输出 t 在数组 a 中的位置否则输出 -1 。
输入n数组 a 和 m 以及 m 个查询的数 t 。
输出对于每个查询的数 t 若数组 a 中有 t 输出 t 在数组 a 中的位置否则输出 -1 。
输入样例
10
1 2 3 4 5 6 7 8 9 10
5
1 100 6 9 11
输出样例
1
-1
6
9
-1
代码
#include bits/stdc.h
using namespace std;
int n,m;
int a[10010];
int main()
{cinn;//数组长度nfor(int i 0;in;i){cina[i];}cinm;//询问次数mfor(int i 0;im;i){int t;//要查询的数cint;int l 0;//数组左端点lint r n-1;//数组右端点rint mid (lr)/2;//数组中间点midwhile(true){if(r-l1)//左端点与右端点靠在了一起{if(a[r]t)//右端点对应的数是要查询的数{coutr1endl;//实际下角标比位置要小1break;//查询完毕直接退出这次查询}else if(a[l]t)//左端点对应的数是要查询的数{coutl1endl;//实际下角标比位置要小1break;//查询完毕直接退出这次查询}else//查询完毕后发现a数组中没有要查询的数{cout-1endl;break;//查询完毕直接退出这次查询}}mid (lr)/2;//更新数组中间点midif(a[mid]t)//要查询的数 t 小于等于中间的数 a[mid] {r mid;//更新缩小查找范围}else if(a[mid]t)//要查询的数 t 大于中间的数 a[mid] {l mid1;//更新缩小查找范围}}}return 0;
} 4.结尾
二分查找算法都讲得这么详细了就给个赞或关注吧
感谢老粉的一路支持也感谢其他人的阅读
