二分查找
时间复杂度o(nlogn)。STL中为lower_bound，upper_bound。
1 int bin_search(int *a,int h,int t,int k) 2 { 3 int lb=h-1,ub=t; 4 5 while(ub-lb>1) { 6 int mid=(lb+ub)/2; 7 if(a[mid]>=k) { 8 ub=mid; 9 } else { 10 lb=mid; 11 } 12 } 13 14 return ub; 15 }
printf("%d %d ",lower_bound(a,a+n,k)-a,upper_bound(a,a+n,k)-a);