PLEASE READ ALL OF THIS IN ORDER TO COMPLETE THE PROGRAM. Write a Java program t

Question

PLEASE READ ALL OF THIS IN ORDER TO COMPLETE THE PROGRAM.

Write a Java program to compare the execution time of linear search and the execution time of binary search.

Within your program, define the linear iterative search method, the linear recursive search method, the binary iterative search method, and the binary recursive method.

Your program will ask the user to input the size (at least 5000) of one array that will store integers with increasing order.

Before invoking the above four methods, your program also will ask the user to input a target integer and an integer for the number of execution times for each method.

Your program will display execution time of each method above.

long currTime = System.currentTimeMillis( ) will assign the current time in term of milliseconds since midnight, January 1, 1970 to

the variable currTime of type of long.

---------------------------------------------------

Here is an example of how to use it:

--------------------------------------------------

public class Example {

public static void main(String[] args) {

String size;

int s;

size = JOptionPane.showInputDialog("Input size of array" + " >= 5000");

s = Integer.parseInt(size);

int[] Array = new int[s];

for (int i = 0; i < Array.length; i++)
{
Array[i] = 100*i + 29;
}

int total = 0;

long startTime = System.currentTimeMillis();
for (int i = 0; i < Array.length; i++)
{
total = total + Array[i];
}
long stopTime = System.currentTimeMillis();

System.out.println("The execution time is: " + (stopTime - startTime) + " milliseconds");
}
}

Explanation / Answer

import java.util.Scanner;

public class SearchAlgo {

   public static int linSearchRec(int[] arr, int low, int high, int searchNum)
   {
       if (low == high)
       {
           return -1;
       }
       else{
           if (arr[low] == searchNum){
               return low;
           }
           else
           {
               return linSearchRec(arr, low + 1, high, searchNum);
           }
       }
   }
   public static int linerSearchIter(int[] arr, int key){

       int size = arr.length;
       for(int i=0;i<size;i++){
           if(arr[i] == key){
               return i;
           }
       }
       return -1;
   }

   public static int binarySearchIter(int[] inputArr, int key) {

       int start = 0;
       int end = inputArr.length - 1;
       while (start <= end) {
           int mid = (start + end) / 2;
           if (key == inputArr[mid]) {
               return mid;
           }
           if (key < inputArr[mid]) {
               end = mid - 1;
           } else {
               start = mid + 1;
           }
       }
       return -1;
   }

   public static int recursiveBinarySearch(int[] sortedArray, int start, int end, int key) {

       if (start < end) {
           int mid = start + (end - start) / 2;
           if (key < sortedArray[mid]) {
               return recursiveBinarySearch(sortedArray, start, mid, key);

           } else if (key > sortedArray[mid]) {
               return recursiveBinarySearch(sortedArray, mid+1, end , key);

           } else {
               return mid;
           }
       }
       return -1;
   }

   public static void main(String[] args) {
       Scanner input = new Scanner(System.in);

       System.out.print("Enter the size of the array: ");
       int size = input.nextInt();
       System.out.print("Enter an array of numbers: ");

       int[] arr = new int[size];

       for(int i=0; i<arr.length; i++)
       {
           arr[i]=input.nextInt();
       }

       System.out.print("Enter the number you want to search: ");
       int search = input.nextInt();
       input.close();

       long startTime = 0;
       long stopTime = 0;
       long elapsedTime = 0;
       int index = -1;

       startTime = System.currentTimeMillis();
       index=linSearchRec(arr, 0, size-1, search);
       stopTime = System.currentTimeMillis();
       elapsedTime = stopTime - startTime;
       System.out.println("Time For Recursive Linear Search: "+elapsedTime);

       startTime = System.currentTimeMillis();
       index=linerSearchIter(arr, search);
       stopTime = System.currentTimeMillis();
       elapsedTime = stopTime - startTime;
       System.out.println("Time For Iterative Linear Search: "+elapsedTime);

       startTime = System.currentTimeMillis();
       index= recursiveBinarySearch(arr, 0, size-1, search);
       stopTime = System.currentTimeMillis();
       elapsedTime = stopTime - startTime;
       System.out.println("Time For Recursive Binary Search: "+elapsedTime);

       startTime = System.currentTimeMillis();
       index=binarySearchIter(arr, search);
       stopTime = System.currentTimeMillis();
       elapsedTime = stopTime - startTime;
       System.out.println("Time For Iterative Binary Search: "+elapsedTime);

       System.out.print("The position of the search item is at array index "+index);
   }

}

/*
Sample run:
Enter the size of the array: 10
Enter an array of numbers: 4 6 8 12 14 16 24 27 34 56
Enter the number you want to search: 5
Time For Recursive Linear Search: 0
Time For Iterative Linear Search: 0
Time For Recursive Binary Search: 0
Time For Iterative Binary Search: 0
The position of the search item is at array index -1
*/

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.