Question

Write a Java program that randomly generates an array of 500,000 integers between 0 and 499,999, and then prompts the user for a search key value. Estimate the execution time of invoking the linearSearch method in Listing A below. Sort the array and estimate the execution time of invoking the binarySearch method in Listing B below. 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;

Here is a sample run:

Enter a search key: 95043⏎

Searching...

The key, 95043, was not found.

Linear search execution time: 11 milliseconds.

Searching...

The key, 95043, was not found.

Binary search execution time: 0 milliseconds.

Must use the following code int he program:

A. Linear Search

public static int linearSearch(int[] list, int key) {

for (int i = 0; i < list.length; i++) {

if (key == list[i])

return i;

}

return -1;

}

B. Binary Search

public static int binarySearch(int[] list, int key) {

int low = 0;

int high = list.length - 1;

while (high >= low) {

int mid = (low + high) / 2;

if (key < list[mid])

high = mid - 1;

else if (key == list[mid])

return mid;

else

low = mid + 1;

}

return –low - 1; // Now high < low, key not found

}

Answer 1

If you have any doubts, please give me comment...

import java.util.Arrays;

import java.util.Random;

import java.util.Scanner;

public class Searching {

    public static void main(String[] args) {

        Scanner scnr = new Scanner(System.in);

        Random rndGen = new Random();

        int arr[] = new int[500000];

        for (int i = 0; i < arr.length; i++) {

            arr[i] = rndGen.nextInt(500000);

        }

        System.out.print("Enter a search key: ");

        int search_key = scnr.nextInt();

        long startTime = System.currentTimeMillis();

        System.out.println("Searching...");

        int pos = linearSearch(arr, search_key);

        long endTime = System.currentTimeMillis();

        long executionTime = endTime - startTime;

        if (pos == -1)

            System.out.println("The key, " + search_key + ", was not found");

        else

            System.out.println("The key, " + search_key + ", was found at index " + pos);

        System.out.println("Linear search execution time: " + executionTime + " milliseconds.");

        Arrays.sort(arr);

        startTime = System.currentTimeMillis();

        System.out.println("Searching...");

        pos = binarySearch(arr, search_key);

        endTime = System.currentTimeMillis();

        executionTime = endTime - startTime;

        if (pos < 0)

            System.out.println("The key, " + search_key + ", was not found");

        else

            System.out.println("The key, " + search_key + ", was found at index " + pos);

        System.out.println("Binary search execution time: " + executionTime + " milliseconds.");

    }

    public static int linearSearch(int[] list, int key) {

        for (int i = 0; i < list.length; i++) {

            if (key == list[i])

                return i;

        }

        return -1;

    }

    public static int binarySearch(int[] list, int key) {

        int low = 0;

        int high = list.length - 1;

        while (high >= low) {

            int mid = (low + high) / 2;

            if (key < list[mid])

                high = mid - 1;

            else if (key == list[mid])

                return mid;

            else

                low = mid + 1;

        }

        return -1; // Now high < low, key not found

    }

}