JAVA JAVA JAVA PLEASE ADD COMMENTS AND SHOW OUTPUT JAVA JAVA JAVA Objective: Imp
ID: 3666745 • Letter: J
Question
JAVA JAVA JAVA
PLEASE ADD COMMENTS AND SHOW OUTPUTJAVA JAVA JAVA
Objective:
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
Sort the array next
Return sorted 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
Explanation / Answer
import java.util.Arrays;
import java.util.Random;
/**
*
* @author Krishna
*/
public class SearchTest {
public static void main(String[] args) {
SearchTest test = new SearchTest();
System.out.println("Welcome to the search tester. We are going to see which algorithm performs the best out of 20 tests");
// stores sum of comparisons in each time of 20 times to get average
int linearSum = 0, binarySum = 0;
// array to hold 1000 numbers
int[] arr = new int[1000];
//Populating array with 1000 random values
arr = test.populateArray(arr);
for (int i = 0; i < 20; i++) {
//gets search item
int searchItem = arr[(int) (Math.random() * 1000) % 1000];
int linear, binary;
// Calls linear search
System.out.println("Searching using linear search");
linear = test.linearSearch(arr, searchItem);
if (linear > 0) {
System.out.println("Found!");
}
// calls binarySearch
System.out.println("Searching using binary search");
binary = test.binarySearch(arr, searchItem);
if (binary > 0) {
System.out.println("Found!");
}
linearSum = linearSum + linear;
binarySum = binarySum + binary;
System.out.println("Linear Checks: " + linear);
System.out.println("Binary Checks: " + binary +" ");
}
System.out.println("The average number of checks for 20 were:");
System.out.println("Linear Search "+ (linearSum/20));
System.out.println("Binary Search "+ (binarySum/20));
}
// linearly searches the array for searchItem and return no of comparisions
private int linearSearch(int[] arr, int searchItem) {
int i;
for (i = 0; i < 1000; i++) {
if (searchItem == arr[i]) {
break;
}
}
return i + 1;
}
// Populates arr woth 1000 random numbers
private int[] populateArray(int[] arr) {
// Storing 1000 random elements in array
Random ran = new Random();
for (int i = 0; i < 1000; i++) {
arr[i] = ran.nextInt(1000);
}
return arr;
}
private int binarySearch(int[] arr, int searchItem) {
Arrays.sort(arr);
return bsearch(arr, 0, arr.length - 1, searchItem, 0);
}
// bianry search algo also counts no of comparisions and stores in count
private int bsearch(int[] arr, int start, int end, int item, int count) {
int middle; // middle element subscript
while (start <= end) {
middle = (start + end) / 2;
if (item == arr[ middle]) {
return count;
} else if (item > arr[ middle]) {
start = middle + 1;
count++;
} else {
end = middle - 1;
count++;
}
bsearch(arr, start, end, item, count);
}
return -1;
}
}
Output :
run:
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: 25
Binary Checks: 5
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 142
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 34
Binary Checks: 7
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 557
Binary Checks: 9
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 357
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 232
Binary Checks: 5
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 244
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 207
Binary Checks: 9
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 874
Binary Checks: 2
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 932
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 645
Binary Checks: 9
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 489
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 196
Binary Checks: 7
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 340
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 792
Binary Checks: 7
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 180
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 333
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 428
Binary Checks: 6
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 681
Binary Checks: 8
Searching using linear search
Found!
Searching using binary search
Found!
Linear Checks: 425
Binary Checks: 7
The average number of checks for 20 were:
Linear Search 405
Binary Search 7
BUILD SUCCESSFUL (total time: 0 seconds)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.