快速排序+查找
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)//二分查找,未找到返回-1 30 { 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)//二分下界查找,无下界返回-1 43 { 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)//二分上届查找,无上届返回-1 55 { 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 }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。