1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn=10000; 7 int f[maxn]; 8 void swap(int &a,int &b){int t=a;a=b;b=t;} 9 10 /*********************************************/11 //所有l均为数组起始下标，所有r均为数组结束下标12 void quicksort(int a[],int l,int r)//快速排序13 {14     if(l<r)15     {16         int t=a[l],i=l,j=r;17         while(i!=j)18         {19             while(t<=a[j] && i<j) j--;20             while(a[i]<=t && i<j) i++;21             if(i<j) swap(a[i],a[j]);22         }23         a[l]=a[i];a[i]=t;24         quicksort(a,l,i-1);25         quicksort(a,i+1,r);26     }27 }28 29 int binary_search(int a[],int l,int r,int val)//二分查找，未找到返回-130 {31     int mid,ans=-1;32     while(l<=r)33     {34         mid=(l+r)>>1;35         if(val>a[mid]) l=mid+1;36         else if(val==a[mid]) return mid;37         else r=mid-1;38     }39     return ans;40 }41 42 int lower_bound(int a[],int l,int r,int val)//二分下界查找，无下界返回-143 {44     int mid,ans=-1;45     while(l<=r)46     {47         mid=(l+r)>>1;48         if(a[mid]<=val) ans=mid,l=mid+1;49         else r=mid-1;50     }51     return ans;52 }53 54 int upper_bound(int a[],int l,int r,int val)//二分上届查找，无上届返回-155 {56     int mid,ans=-1;57     while(l<=r)58     {59         mid=(l+r)>>1;60         if(a[mid]>=val)  ans=mid,r=mid-1;61         else l=mid+1;62     }63     return ans;64 }65 /*********************************************/66 67 int main()68 {69     int i,n;70     while(~scanf("%d",&n))71     {72         for(i=1;i<=n;i++) scanf("%d",f+i);73         quicksort(f,1,n);74         for(i=1;i<=n;i++) printf("%d ",f[i]);75         puts("");76         int t,p;77         puts("5次二分查找");t=5;78         while(t--){scanf("%d",&p);printf("%d\n",binary_search(f,1,n,p));}79         puts("5次二分下界查找");t=5;80         while(t--){scanf("%d",&p);printf("%d\n",lower_bound(f,1,n,p));}81         puts("5次二分上界查找");t=5;82         while(t--){scanf("%d",&p);printf("%d\n",upper_bound(f,1,n,p));}83     }84     return 0;85 }