# Array: Execution Time

Question: Write a program that randomly generates an array of 100,000 integers and a key.
Estimate the execution time of invoking the linearSearch method.
Sort the array and estimate the execution time of invoking the binarySearch method.
You can use the following code template to obtain the execution time:
long startTime = System.nanoTime(); perform the task;
long endTime = System.nanoTime();
long executionTime = endTime − startTime;

Sample Output:

Time taken in linear search: 1151359 nanoseconds
Time taken in binary search: 1166 nanoseconds

```package Ch7;

/*
Q: Write a program that randomly generates an array of 100,000 integers and a key.
Estimate the execution time of invoking the linearSearch method.
Sort the array and estimate the execution time of invoking the binarySearch method.
You can use the following code template to obtain the execution time:
long startTime = System.nanoTime(); perform the task;
long endTime = System.nanoTime();
long executionTime = endTime − startTime;
*/

import java.util.Arrays;

public class Ex16 {

final static int SIZE= 100000;

//method for linear search
public static long linearSearch(int[] array, int key){
boolean found=false;

//get the start time
long startTime= System.nanoTime();
for(int i=0; i<array.length; i++){
if(key==array[i]){
found=true;
}
}
//get the end time
long endTime= System.nanoTime();

//return the difference between the end and start time
return endTime-startTime;
}

//method for binary search
public static long binarySearch(int[] array, int key){
boolean found=false;
//binary search requires a sorted array
Arrays.sort(array);
int lowBound= 0, upBound= array.length-1;

//get the start time
long startTime= System.nanoTime();
while(upBound>lowBound){
int mid=(upBound+lowBound)/2;
if(key<array[mid]){
upBound=mid-1;
} else if (key>array[mid]){
lowBound=mid+1;
} else {
found=true;
break;
}
}
//get the end time
long endTime= System.nanoTime();

//return the difference between the end and start time
return endTime-startTime;
}

//method to generate random numbers
public static void generateArray(int[] array){
for(int i=0; i<SIZE; i++){
array[i]=(int)(Math.random()*100);
}
}

public static void main (String [] args){
int[] array= new int[SIZE];
generateArray(array);
//generate a random key
int key= (int)(Math.random()*100);
System.out.println("Time taken in linear search: " + linearSearch(array, key) + " nanoseconds");
System.out.println("Time taken in binary search: " + binarySearch(array, key) + " nanoseconds");
}
}```

This site uses Akismet to reduce spam. Learn how your comment data is processed.