PLEASE READ ALL OF THIS IN ORDER TO COMPLETE THE PROGRAM. Write a Java program t
ID: 3733875 • Letter: P
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.
Explanation / Answer
Please find the code below with detailed inline comments.
CODE
==================
import java.util.Random;
import java.util.Scanner;
public class Demo {
public static int binarySearch(int[] array, int search) {
int start = 0;
int end = array.length - 1;
while (start <= end) {
int middle = (start + end) / 2;
if (search < array[middle]) {
end = middle - 1;
}
if (search > array[middle]) {
start = middle + 1;
}
if (search == array[middle]) {
return middle;
}
}
return -1;
}
public static int binarySearchRecursive(int[] array, int search, int start, int end) {
int middle = (start + end)/2;
if(end < start){
return -1;
}
if (search < array[middle]){
return binarySearchRecursive(array, search, start, middle - 1);
}
if (search > array[middle]){
return binarySearchRecursive(array, search, middle + 1, end);
}
if (search == array[middle]){
return middle;
}
return -1;
}
public static int linearSearch(int arr[], int x) {
for (int i = 0; i < arr.length; i++)
{
// Return the index of the element if the element
// is found
if (arr[i] == x)
return i;
}
// return -1 if the element is not found
return -1;
}
public static int linearSearchRecursive(int arr[], int l, int r, int x) {
if (r < l)
return -1;
if (arr[l] == x)
return l;
return linearSearchRecursive(arr, l+1, r, x);
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the size of the array(atleast 5000): ");
int size = sc.nextInt();
Random rand = new Random();
if(size < 5000)
size = 5000;
int arr[] = new int[size];
for(int i=0; i<size; i++) {
arr[i] = rand.nextInt(100);
}
int target, times;
System.out.print("Enter the target: ");
target = sc.nextInt();
System.out.print("Enter the number of execution times for each method: ");
times = sc.nextInt();
long startTime, endTime;
for(int i=0; i<times; i++) {
System.out.println(" Iteration times " + (i+1));
startTime = System.currentTimeMillis();
System.out.println(startTime + "sec");
System.out.print("Using Iterative Binary Search: Element found: ");
System.out.println(binarySearch(arr, target) != -1 ? "True" : "False");
endTime = System.currentTimeMillis();
System.out.println("Time taken = " + (endTime - startTime) + " milliseconds");
startTime = System.currentTimeMillis();
System.out.println(startTime + "sec");
System.out.print("Using Recrusive Binary Search: Element found: ");
System.out.println(binarySearchRecursive(arr, target, 0, arr.length-1) != -1 ? "True" : "False");
endTime = System.currentTimeMillis();
System.out.println("Time taken = " + (endTime - startTime) + " milliseconds");
startTime = System.currentTimeMillis();
System.out.println(startTime + "sec");
System.out.print("Using Iterative Linear Search: Element found: ");
System.out.println(linearSearch(arr, target) != -1 ? "True" : "False");
endTime = System.currentTimeMillis();
System.out.println("Time taken = " + (endTime - startTime) + " milliseconds");
startTime = System.currentTimeMillis();
System.out.print("Using Recrusive Linear Search: Element found: ");
System.out.println(linearSearchRecursive(arr, 0, arr.length-1, target) != -1 ? "True" : "False");
endTime = System.currentTimeMillis();
System.out.println("Time taken = " + (endTime - startTime) + " milliseconds");
System.out.println();
}
sc.close();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.