1.分治算法介绍

分治算法#xff0c;大概就是将一个大问题拆解成若干个小问题#xff0c;将小问题一一解决#xff0c;大问题也就迎刃而解。

它包含了多种算法#xff0c;比如递归、递推等。

这里就讲解一下其…大家好今天进入一个实用算法分治算法。

1.分治算法介绍

分治算法大概就是将一个大问题拆解成若干个小问题将小问题一一解决大问题也就迎刃而解。

它包含了多种算法比如递归、递推等。

这里就讲解一下其中比较经典的一个算法二分查找算法。

2.二分查找算法介绍

二分查找算法适用于在有序数组中寻找某个数其时间复杂度较正常的顺序查找而言大大减小从On的效率提高到了Olog

如要在100个数中查询一个数在最坏的情况下顺序查找需要循环100次而二分查找只需要循环不到10次。

二分查找算法基本思想

0;in;i){cina[i];}cinm;//询问次数mfor(int

0;im;i){int

(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)//要查询的数

a[mid]