superchaoran的个人空间

/*filename:P6Q15
 *Name:Wang Chaoran
Desciprtion:
15 (Timing execution)
Write a program that randomly generates an array of 100000 integers
and a key. Estimate the execution time of invoking the linearSearch
method in Listing 6.6. Sort the array and estimate the execution time
of invoking the binarySearch method in Listing 6.7. You can use the
following code template to obtain the execution time:

long startTime = System.currentTimeMillis();
perform the task;
long endTime = System.currentTimeMillis();
long executionTime = endTime - startTime;
*/
class p6Q15{
  public static void main(String[] args){
  final int task = 100000;
  int[] randomNum = new int[task];
 
  for(int i =0;i<=randomNum.length-1;i++)
    randomNum[i] = (int)(Math.random()*(task+1));
 
  int key = (int)(Math.random()*(task+1));
  sort2(randomNum);

 
  System.out.println("Key is: "+key);
 
  long startTime1 = System.currentTimeMillis() * 1000;
  int linear =  linearSearch(randomNum,key);
  long endTime1 = System.currentTimeMillis() * 1000;
  long startTime2 = System.currentTimeMillis() * 1000;
  int binary = binarySearch(randomNum,key);
  long endTime2 = System.currentTimeMillis() * 1000;
 
  //System.out.println("(Using linearSearch)Position in array is: "+linear);
   System.out.println("(Using linearSearch)Position in array is: "+linear);
  System.out.println("(Using binarySearch)Position in array is: "+binary);

 
  System.out.println("Perform linearSearch use " +(endTime1-startTime1)+" milli seconds.");
  System.out.println("Perform binarySearch use " +(endTime2-startTime2)+" milli seconds.");
  }
 
  static void sort1(int[] array){
    for(int i=array.length-1; i>=1; i--){
      int max = array[0];
          int index = 0;
      for(int j =1; j<=i;j++){
        if(max<array[j]){
        max=array[j];
        index = j;
        }
      }
      if(index!=i){
      array[index]=array[i];
      array[i]=max;
      }
  }
  }
 
  static void sort2(int[] array) {
    for(int i=1; i<array.length; i++) {
      int j;
      int current = array[i];
    for(j = i-1;j>=0&&array[j]>current;j--)
      array[j+1]=array[j];
    array[j+1]=current;
    }
  }
 
  static void print(int[] array){
    for(int i=0;i<=array.length-1;i++)
      System.out.print(array[i]+" ");
    System.out.println();
  }
 
  static int linearSearch(int[] array,int key){
    for(int i=0;i<array.length;i++){
    if(array[i]==key)
      return i;
    }
    return -1;
  }
 
 
  static int binarySearch(int[] array,int key){
    int low=0;
    int mid;
    int high = array.length-1;
    while(low<=high){
      mid=(low+high)/2;
      if(array[mid]>key)
        high = mid - 1;   
      else if(array[mid]==key)
        return mid;
      else
        low = mid +1;
    }
    return -low-1;
  }
 
}