find an algorithm for finding the min and max of n numbers by using fewer
than 3n/2 comparisions. ^_^
global int x[n];
void minmax(int i, j, int& min, max)
{
if (i==j)
min=max=x[i];
elseif (j-i==1)
max=x[i]>x[j]?x[i]:x[j];
min=x[i]+x[j]-max;
else
int min1,max1,min2,max2;
int k=(i+j)/2;
minmax(i,k, min1, max1);
minmax(k+1, j, min2, max2);
min=min1>min2?min2:min1;
max=max1>max2?max1:max2;
}
int min, max;
minmax(0,n-1, min, max);
It uses divide and conquer stratege, and has complexity of about 3/2n
阅读(851) | 评论(0) | 转发(0) |
