1.1.39随机匹配。编写一个使用BinarySearch的程序，它从命令行接受一个整型参数T,并会分别针对N=10^3、10^4、10^5和10^6将以下实验运行T遍：生成两个大小为N的随机6位正整数数组并找出同时存在于两个数组中的整数的数量。打印一个表格，对于每个N,给出T次实验中该数量的平均值。
解：
import java.util.Arrays;
public class Test
{
public static void main(String[] args)
{
int T=Integer.parseInt(args[0]);
int repeatTime;
int[] a;
int[] b;
for (int N=1000;N<=1000000;N=N*10)
{
repeatTime=0;
a=new int[N];
b=new int[N];
for (int i=0;i<T;i++)
{
//generate array;
for (int j=0;j<N;j++)
{
a[j]=StdRandom.uniform(100000,1000000);
b[j]=StdRandom.uniform(100000,1000000);
}
//seach repeart
Arrays.sort(b);
for(int k=0;k<N;k++)
if(rank(a[k],b)>-1) repeatTime++;
}//end for T
StdOut.printf("T=%3d,N=%7d,AverageRepeartTime=%.2f
",T,N,1.0*repeatTime/T);
}//end for N
}//end main
public static int rank(int key,int[]a)
{
int lo=0;
int hi=a.length-1;
while (lo<=hi)
{
int mid=lo+(hi-lo)/2;
if (key<a[mid]) hi=mid-1;
else if(key>a[mid]) lo=mid+1;
else return mid;
}
return -1;
}//end BinarySearch Rank
}//end class Test
