Question
In: Computer Science
I need original java code that completes this program and gets it to print out results...
I need original java code that completes this program and gets it to print out results just like in the example. Also please upload answer in a word document format only.
Implement both linear search and binary search, and see which one performs better given an array 1,000 randomly generated whole numbers (between 0-999), a number picked to search that array at random, and conducting these tests 20 times. Each time the search is conducted the number of checks (IE number of times the loop is ran or the number of times the recursive method is called) needs to be counted and at the end the total number of checks should be averaged.
A few notes
Each algorithm (linear search and binary search) is ran 20 times
Each time a new sorted array of whole numbers is created and populated with random values from 0-999
A value to be searched in the said array is randomly selected from the range 0-999
Each algorithm must display if that number was successfully found
Each algorithm must display the number of checks it took to determine the above answer
It is advisable to create a method that returns the sorted array
Populate the array with random numbers
Search the array next
Return whether or not the value was found in the array
Implement both searches as a method
However instead of returning whether or not it found the number it should return the number of checks.
Whether the value is or is not found can be printed in the method
Binary search is fairly simple to create using recursion
Do not count the out of bounds or stopping index as a check
Example:
Welcome to the search tester. We are going to see which algorithm performs the best out of 20 tests
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 753
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 834
Binary Checks: 10
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks: 1000
Binary Checks: 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 515
Binary Checks: 6
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 757
Binary Checks: 7
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 395
Binary Checks: 9
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 117
Binary Checks: 7
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 334
Binary Checks: 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 521
Binary Checks: 9
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks: 1000
Binary Checks: 10
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks: 1000
Binary Checks: 10
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks: 1000
Binary Checks: 10
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks: 1000
Binary Checks: 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 901
Binary Checks: 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 626
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 361
Binary Checks: 9
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 630
Binary Checks: 9
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 443
Binary Checks: 7
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 818
Binary Checks: 10
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 288
Binary Checks: 7
The average number of checks for 20 were:
Linear Search 664
Binary Search 8
Solutions
Expert Solution
RandomNumbers.java :
import java.util.Random;
import java.util.Scanner;
public class RandomNumbers {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Random r = new Random();
int arr[] = new int[1000];
for(int i=0;i<1000;i++)
arr[i] = r.nextInt()%1000 + 1;
int linearcount[] = new int[20];
int binarycount[] = new int[20];
System.out.println("Welcome to the search tester. We are going to see which algorithm performs the best out of 20 tests");
for(int i=0;i<20;i++){
System.out.print("\nEnter key element:");
int key = sc.nextInt();
System.out.println("Searching using linear search");
int lcount = linearSearch(arr,key);
System.out.println("Searching using binary search");
int bcount = binarySearch(arr,key);
System.out.println("Linear Checks:"+lcount);
System.out.println("Binary Checks:"+bcount);
linearcount[i] = lcount;
binarycount[i] = bcount;
}
double linear_sum = 0,binary_sum =0,linear_avg = 0,binary_avg = 0;
System.out.println("\nThe average number of checks for 20 were");
for(int i=0;i<20;i++){
linear_sum += linearcount[i];
binary_sum += binarycount[i];
}
linear_avg = linear_sum /20;
binary_avg = binary_sum /20;
System.out.println("Linear Search: "+linear_avg);
System.out.println("Binary Search: "+binary_avg);
}
public static int linearSearch(int a[],int key){
int compCount = 0;
for(int i=0;i<1000;i++){
compCount++;
if(a[i] == key){
System.out.println("Found!");
return compCount;
}
}
System.out.println("Not Found");
return compCount;
}
public static int binarySearch(int a[],int key){
int compCount = 0;
int i,temp;
for(i=0;i<1000;i++){
for(int j=i+1;j<1000;j++){
if(a[i]>a[j]){
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
int mid,low = 0,high = 1000-1;
while(low<=high){
mid = (low + high)/2;
compCount++;
if(a[mid] == key){
System.out.println("Found!");
return compCount;
}
else if(a[mid] > key){
high = mid - 1;
}
else{
low = mid + 1;
}
}
System.out.println("Not Found");
return compCount;
}
}
Sample Input & Output :
Welcome to the search tester. We are going to see which algorithm performs the best out of 20 tests
Enter key element:839
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks:3
Binary Checks:9
Enter key element:45
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks:516
Binary Checks:10
Enter key element:34
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:57
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks:521
Binary Checks:9
Enter key element:29
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks:508
Binary Checks:9
Enter key element:71
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks:526
Binary Checks:10
Enter key element:39
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:42
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:896
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:734
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks:868
Binary Checks:9
Enter key element:234
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks:606
Binary Checks:10
Enter key element:436
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:509
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:987
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks:994
Binary Checks:10
Enter key element:765
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:345
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:382
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:231
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:56
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
Enter key element:69
Searching using linear search
Not Found
Searching using binary search
Not Found
Linear Checks:1000
Binary Checks:10
The average number of checks for 20 were
Linear Search: 827.1
Binary Search: 9.8
venereology answered 2 years agoRelated Solutions
I need it in java. Write a program that will print if n numbers that the...
I need to make this into a Java Code: Write a program that prompts the user...
Write a complete Java program to print out the name bob
I need a java code Write a simple program to prompt the user for a number...
I need the Java Code and Flowchart for the following program: Suppose you are given a...
i need this program to also print out the number of combinations #include <stdio.h> #include <string.h>...
I need this Java code transform to Python Code PROGRAM: import java.util.Scanner; public class Main {...
In java coding, write a program that will print out a representation of a “W” using...
Write a Java program that accepts a sequence of commands and print out the number of...
I NEED IT PRINT IN THIS FORM JAVA How is a Java source file executed? 1....
- Problem 1: In the figure to the right, m1=20.0kg and α=53.1o . The coefficient of kinetic...
- A palindrome is a string whose reversal is identical to the string. For example, 110010011 is...
- Explain how the shape of the load duration curve for a particular system affects the selection...
- For physics discussion post. Please TYPE the response as I struggle with reading written information. Explain...
- Consider a file system using a multi-level indexing scheme in inodes as the file organization. In...
- 1a) A sample of a new cleaning product, "Joe's Famous Bleach Cleaner," with a mass of...
- TRANSPARANT DATA ENCRYPTION TOPIC INTRODUCTION 150WORDS, DESCRIPTION 250 WORDS, CONCLUTION 150 WORDS USE OWN WORDS 500 WORDS....