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 } 

 關於二分到現在基本講完了，大家拜拜~~