分治算法——二分查找（c++）（详解）

大家好，今天进入一个实用算法：分治算法。

1.分治算法介绍

分治算法，大概就是将一个大问题拆解成若干个小问题，将小问题一一解决，大问题也就迎刃而解。它包含了多种算法，比如递归、递推等。这里就讲解一下其中比较经典的一个算法：二分查找算法。

2.二分查找算法介绍

二分查找算法适用范围、优点

二分查找算法，适用于在有序数组中寻找某个数，其时间复杂度较正常的顺序查找而言大大减小，从O（n）的效率提高到了O（log 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 = mid+1 ，然后接着进行步骤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()
{cin>>n;//数组长度nfor(int i = 0;i<n;i++){cin>>a[i];}cin>>m;//询问次数mfor(int i = 0;i<m;i++){int t;//要查询的数cin>>t;int l = 0;//数组左端点lint r = n-1;//数组右端点rint mid = (l+r)/2;//数组中间点midwhile(true){if(r-l<=1)//左端点与右端点靠在了一起{if(a[r]==t)//右端点对应的数是要查询的数{cout<<r+1<<endl;//实际下角标比位置要小1break;//查询完毕，直接退出这次查询}else if(a[l]==t)//左端点对应的数是要查询的数{cout<<l+1<<endl;//实际下角标比位置要小1break;//查询完毕，直接退出这次查询}else//查询完毕后，发现a数组中没有要查询的数{cout<<-1<<endl;break;//查询完毕，直接退出这次查询}}mid = (l+r)/2;//更新数组中间点midif(a[mid]>=t)//要查询的数 t 小于等于中间的数 a[mid] {r = mid;//更新缩小查找范围}else if(a[mid]<t)//要查询的数 t 大于中间的数 a[mid] {l = mid+1;//更新缩小查找范围}}}return 0;
}

4.结尾

二分查找算法都讲得这么详细了，就给个赞或关注吧！

感谢老粉的一路支持，也感谢其他人的阅读！