二分模板

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 const int N=10000;
 5 int a[N],n,x;
 6 int binarysearch(int a[],int x,int left,int right)
 7 {
 8     if(left>right)return -1;
 9     int mid=(left+right)/2;
10     if(x==a[mid])return mid+1;
11     if(x<a[mid])
12        return binarysearch(a,x,left,mid-1);
13     else//即为x>a[mid]
14        return binarysearch(a,x,mid+1,right);
15 }
16 //下面写一下二分的简化代码，共有两种
17 int bsearch_1(int a[],int x,int l,int r)
18 {
19     //与上面的代码相比，这里将a[mid]==x的情况不分开讨论
20     //通过while循环实现递归
21     while(l<r)//>=x最小的值
22     {
23         int mid=l+r>>1;
24         if(a[mid]<x)l=mid+1;
25         else
26             r=mid;
27     }
28     return l+1;
29 }
30 int bsearch_2(int a[],int x,int l,int r)
31 {//<=x最大的值
32     while(l<r)
33     {
34         int mid=l+r+1>>1;
35         if(a[mid]<=x)l=mid;
36         else
37             r=mid-1;
38     }
39     return l+1;
40 }
41 int main()
42 {
43     cout<<"二分查找一定要在有序序列中进行,当然输入非有序序列，也可将其先排列为有序"<<endl;
44     cout<<"n=";
45     cin>>n;
46     cout<<"需要搜索的数组：";
47     for(int i=0;i<n;i++)
48         cin>>a[i];
49     sort(a,a+n);
50     cout<<"排列好的有序数组为：";
51     for(int i=0;i<n;i++)
52         cout<<a[i]<<" ";
53     cout<<endl<<"需要搜索的数：";
54     cin>>x;
55     cout<<"该数在有序数组中的位置为："<<endl<<"方法1："<<binarysearch(a,x,0,n-1)<<endl;
56     cout<<"方法2："<<bsearch_1(a,x,0,n-1)<<endl<<"方法3："<<bsearch_2(a,x,0,n-1);
57     return 0;
58 }