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");
    }
}

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published.

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

%d bloggers like this: