i would prfer java implement linearSearch(a,key) and binarySearch(a,key) functio

Question

i would prfer java

implement linearSearch(a,key) and binarySearch(a,key) functions.

I need to get stop 5 6 7 8

1. Request the user to enter a positive integer, and call it n. (n = 10^5 )

2. Generate n random integers between -1000 to 1000 and save them in array a.

3. Sort a (you can use any sorting algorithm you want. If you are using MATLAB, you can call the sort function to sort your numbers)

4. Now to have the worst-case scenario, set the value of the key to 5000 to make sure it does not exist in the array.

5. Run each function once to calculate the worst-case running time when n = 10^5 .

6. Calculate how much time your machine takes to run one single step

7. Now estimate the worst-case running time for each algorithm when n=10^7

8. Now repeat step 1-3 for n = 10^7 and compare the actual running time with your answer in step 5

Explanation / Answer

Solution:

code:

package chegg;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class SearchTest {

// The index of the element in the array[] a will be returned by this method
static int iterativeLinearSearch(int array[], int n, int a)
{
for (int index = 0; index < n; index++)
{
//If the elemnt is found then the index of the element will be returned
if (array[index] == a)
return index;
}
  
//-1 will be returned if the element is not found in the array
return -1;
}
  
// The index of the element in the array[] a will be returned by this method
static int recursiveLinearSearch(int array[], int l, int r, int a)
{
if (r < l)
return -1;
if (array[l] == a)
return l;
return recursiveLinearSearch(array, l+1, r, a);
}
  
// The index of the element a in the array[] a will be returned by this method else -1
static int recursiveBinarySearch(int array[], int left, int right, int a)
{
if (right>=left)
{
int middle = left + (right - left)/2;

// If the element is at the middle, basically binary seracch
if (array[middle] == a)
return middle;

// If element is smaller than mid, then it can only
// be present in left subarrayay
if (array[middle] > a)
return recursiveBinarySearch(array, left, middle-1, a);

// Else the element can only be present in right
// subarrayay
return recursiveBinarySearch(array, middle+1, right, a);
}

// We reach here when element is not present in arrayay
return -1;
}
  
// A iterative binary search function. It returns location of a in
// given arrayay array[l..r] if present, otherwise -1
static int iterativeBinarySearch(int array[], int left, int right, int a)
{
while (left <= right)
{
int z = left + (right-left)/2;
  
// Check if a is present at mid
if (array[z] == a)
return z;
  
// If a greater, ignore left half
if (array[z] < a)
left = z + 1;
  
// If a is smaller, ignore right half
else
right = z - 1;
}
  
// if we reach here, then element was not present
return -1;
}
  
public static Random rn = new Random();

public static void fillArray(int []array, int n)
{
for(int i = 0; i < n; i++)
{
array[i] = (rn.nextInt()%20000)-10000;
}
}

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

int n;
while(true)
{
System.out.print("Enter number of element in array (atleast 5000): ");
n = sc.nextInt();
if (n < 5000)
{
System.out.println("Number is below 5000 try again.");
}
else
{
break;
}
}
int[] array = new int[n];

fillArray(array, n);
Arrays.sort(array);
System.out.print("Enter a number to find: ");
int num;
num = sc.nextInt();

System.out.print("Enter number of execution: ");
int execN = sc.nextInt();
long time;
double avgTimeMs;

time = 0;
for (int i = 0; i < execN; i++)
{
long startTime = System.currentTimeMillis( );
iterativeLinearSearch(array, n, num);
time += System.currentTimeMillis( ) - startTime;
}
avgTimeMs = (double)(time)/execN;
System.out.println("Average time taken by iterative linear search: " + avgTimeMs);

time = 0;
for (int i = 0; i < execN; i++)
{
long startTime = System.currentTimeMillis( );
recursiveLinearSearch(array, 0, n-1, num);
time += System.currentTimeMillis( ) - startTime;
}
avgTimeMs = (double)(time)/execN;
System.out.println("Average time taken by recursive linear search: " + avgTimeMs);

time = 0;

for (int i = 0; i < execN; i++)
{
long startTime = System.currentTimeMillis( );
iterativeBinarySearch(array, 0, n-1, num);
time += System.currentTimeMillis( ) - startTime;
}
avgTimeMs = (double)(time)/execN;
System.out.println("Average time taken by iterative binary search: " + avgTimeMs);

time = 0;
for (int i = 0; i < execN; i++)
{
long startTime = System.currentTimeMillis( );
recursiveBinarySearch(array, 0, n-19, num);
time += System.currentTimeMillis( ) - startTime;
}
avgTimeMs = (double)(time)/execN;
System.out.println("Average time taken by recursive binary search: " + avgTimeMs);
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

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