算法中,有一种比线性查找算力费得更少的一种算法思想,叫“分治”,今天讲的是分治里的二分查找:
借助 (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 }
关于二分到现在基本讲完了,大家拜拜~~
标签:二分,int,元素,c++,算法,查找 From: https://www.cnblogs.com/xuexue1234/p/cpluspluserfen_.html