Hey could someone please help with this I posted what i have so far under the ex
ID: 3666681 • Letter: H
Question
Hey could someone please help with this
I posted what i have so far under the example that should be followed
Written in Java Please
Thank You
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
import java.util.*;
import java.util.Random;
import java.util.Arrays;
public class SearchingAlgorithms {
public static void main(String[] args) {
int value=r.nextInt(1000);
}
public static Random r=new Random();
public static int[] RandomArray() {
int [] array = new int[1000];
for (int i = 0; i < array.length; i++) {
array[i] = r.nextInt(1000);
}
Arrays.sort(array);
return array;
}
// Iterative way
public static boolean linearSearchIterative(int[] array, int value) {
for (int i = 0; i < array.length; i++) {
if (array[i] == value) {
return true;
}
}
return false;
}
// Recursive way
public static boolean linearSearchRecursive(int[] array, int value, int index) {
if (array[index] == value) {
return true;
} else {
index++;
if (index >= array.length) {
return false;
} else {
return linearSearchRecursive(array, value, index);
}
}
}
public static boolean binarySearchRecursive(int[] a, int value, int minIndex, int maxIndex) {
int midIndex = ((maxIndex + minIndex) / 2);
if (minIndex > maxIndex) {
return false;
}
if (a[midIndex] == value) {
return true;
} else {
if (value > a[midIndex]) // Searches the top half
{
return binarySearchRecursive(a, value, midIndex + 1, maxIndex);
} else // searches the bottom half
{
return binarySearchRecursive(a, value, minIndex, midIndex - 1);
}
}
}
}
Explanation / Answer
Code:
import java.util.*;
import java.util.Random;
import java.util.Arrays;
public class SearchingAlgorithms {
public static void main(String[] args) {
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++)
{
int[] a= RandomArray();//create an array of 1000 random elements
Arrays.sort(a); // sort the array
int value=r.nextInt(1000); // create a random value from 1 to 1000
System.out.println("Searching "+value+" using liner search");
int count = linearSearchIterative(a,value); // search for value in array using lionear search
System.out.println("Searching "+value+" using binary search");
int count1 = binarySearchRecursive(a,value,0,a.length-1,0);// search for value in array using binary search
System.out.println("Linear checks = "+count);//print linear count
System.out.println("Binary checks = "+count1);// print binary count
}
}
public static Random r=new Random();
public static int[] RandomArray() {
int [] array = new int[1000];
for (int i = 0; i < array.length; i++) {
array[i] = r.nextInt(1000);
}
Arrays.sort(array);
return array;
}
// Iterative way of linear search that returns number of checks
public static int linearSearchIterative(int[] array, int value) {
for (int i = 0; i < array.length; i++) {
if (array[i] == value) {
System.out.println("Found");// print found if the value is found in array
return i;
}
}
System.out.println("Not Found");// print Not found if the value is present in array
return array.length;
}
// Recursive way
public static int linearSearchRecursive(int[] array, int value, int index) {
if (array[index] == value) {
System.out.println("Found");// print found if the value is found in array
return index;
} else {
index++;
if (index >= array.length) {
System.out.println("Not Found");// print Not found if the value is present in array
return index;
} else {
return linearSearchRecursive(array, value, index);
}
}
}
public static int binarySearchRecursive(int[] a, int value, int minIndex, int maxIndex, int checks) {
int midIndex = ((maxIndex + minIndex) / 2);
if (minIndex > maxIndex) {
System.out.println("Not Found");// print Not found if the value is present in array
return checks;
}
if (a[midIndex] == value) {
System.out.println("Found");// print found if the value is found in array
return checks+1;
} else {
if (value > a[midIndex]) // Searches the top half
{
return binarySearchRecursive(a, value, midIndex + 1, maxIndex,checks+1);
} else // searches the bottom half
{
return binarySearchRecursive(a, value, minIndex, midIndex - 1,checks+1);
}
}
}
}
Output: