演算法中，有一種比線性查找算力費得更少的一種演算法思想，叫“分治”，今天講的是分治里的二分查找：
借助 (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 }
關于二分到現在基本講完了，大家拜拜~~
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/553955.html
標籤：其他
下一篇：返回列表