c++算法:二分

算法中,有一种比线性查找算力费得更少的一种算法思想,叫“分治”,今天讲的是分治里的二分查找:

借助 (low+high)/2公式,找到搜索区域内的中间元素。图 1 中,搜索区域内中间元素的位置是 ⌊(1+10)/2⌋=5,因此中间元素是 27,此元素显然不是要找的目标元素。然后就是缩小范围。

 下面就是一个二分查找的c++程序:

1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int a[500005];
 5 int n;
 6 bool sreach(int key)
 7 {
 8 int mid,left=1,right=n;
 9 while(left<=right)//遍历a[]
10 {
11 mid=(left+right)/2;//寻找中间值
12 if(a[mid]==key)//判断是否查到
13 {
14 return true;
15 }
16 else if(a[mid]<key)
17 {
18 left=mid+1;//缩小范围
19 }
20 else
21 {
22 right=mid-1;//缩小范围
23 }
24 }
25 return false;
26 }
27 int main()
28 {
29 int t,m;
30 scanf("%d",&n);
31 for(int i=1;i<=n;i++)
32 {
33 scanf("%d",&a[i]);
34 }
35 sort(a+1,a+n+1);
36 scanf("%d",&t);
37 while(t--)
38 {
39 cin >> m;
40 if(sreach(m))
41 {
42 printf("YES");
43 cout << endl;
44 }
45 else
46 {
47 printf("NO");
48 cout << endl;
49 }
50 }
51 return 0;
52 }

 关于二分到现在基本讲完了,大家拜拜~~

作者:薛晓明c++算法原文地址:https://www.cnblogs.com/xuexue1234/p/cpluspluserfen_.html

%s 个评论

要回复文章请先登录注册