Homework SourseTask Write a Java program to implement recursive binary sear
Task: Write a Java program to implement recursive binary search and linear search. You can use an array of integers of fixed size 2^20 = 1048576. The array should be filled with random integers between 1 and 1,000,000. Set up a random target also in that range. Sort the array before applying binary search. Apply the methods separately on the array and record the time taken by the methods in nanoseconds. Do not include pre-processing time (creation of array & filling up with random integers, creating random target integer, and sorting the array before binary search) in the search time calculation. You need to fill up the following table and create plot using the recorded data. You need record 10 runs of the comparison. That means your program should perform the above steps 10 times. Each time a new array with newly generated random numbers will be used. The target should also be changed. However, the array size will remain same (2^20) for all these runs.
***Don\'t just copy and paste***********
Solution
Solution:
// import required packages
import java.util.Random;
import java.util.Arrays;
import java.lang.*;
// class to perform lineatr and binary search
class recBinLinSrch
{
// main method
public static void main(String[] args)
{
// declare the required variables
int[] primaryAry = new int[1048576];
int[] sortedAry = new int[1048576];
int lp1,in1,in2,lp;
int rnd_target;
// loop to perfromt array generation and search minimum 10 times
for (lp=0;lp<=10;lp++)
{
// code to generate array with random values
Random rnd_gen= new Random();
for(lp1=0;lp1<1048576;lp1++)
primaryAry[lp1]=rnd_gen.nextInt(1000000)+1;
// code to generate search value
rnd_target=rnd_gen.nextInt(1000000);
// backup of proimary array
sortedAry=primaryAry;
Arrays.sort(sortedAry);
System.out.println(\"\ \ Random Target to Search : \"+rnd_target);
// code to get starting time
long LSstartTime = System.nanoTime();
System.out.println(\"\ ----Linear Search----\ \");
// Code for recursive linear search
//in1=reclinear_search(primaryAry,rnd_target,0);
//System.out.println(\"\ Value Found at
ARRAY[\"+in1+\"] location\");
// code for iterative linear search
linear_search(primaryAry,rnd_target);
// compute total process time
long LSestimatedTime = System.nanoTime() -
LSstartTime;
System.out.println(\"\ Time Taken in Linear Search
(NanoSeconds) : \"+LSestimatedTime);
// code to get starting time
long bistartTime = System.nanoTime();
//code to perform recursive binary search
System.out.println(\"\ ----Binary Search----\ \");
in2=Binary_Search(sortedAry,0,1048575,rnd_target);
System.out.println(\"\ Value Found at ARRAY[\"+in2+\"]
location\");
// compute total process time
long biestimatedTime = System.nanoTime() –
bistartTime;
System.out.println(\"\ Time Taken in Binary Search (NanoSeconds): \"+biestimatedTime);
}
}
// method for recursive linear search
/*static int reclinear_search(int data[],int key,int
stindx)
{
if (stindx == data.length-1)
{
return -1;
}
if (data[stindx] == key)
{
return stindx;
}
else
return reclinear_search(data,key,++stindx);
}*/
// code for linear search
static void linear_search(int p_Array[],int random_t)
{
boolean flag=false;
for(int i=0;i<1048576;i++)
{
if(p_Array[i]==random_t)
{
System.out.println(\"\ Value Found at
ARRAY[\"+i+\"]location\");
flag=true;
}
}
if(flag==false)
{
System.out.println(\"\ Value Not Found in ARRAY \");
}
}
// code for recursive binary search
public static int Binary_Search(int[] sortedAry, int start,
int end, int key) {
if (start < end)
{
int mid = (start + end) / 2;
if (key < sortedAry[mid])
{
return Binary_Search(sortedAry, start, mid,
key);
} else if (key > sortedAry[mid])
{
return Binary_Search(sortedAry, mid+1, end ,
key);
} else if (key ==sortedAry[mid])
{
return mid;
}
}
return -1;
}
}
Result:
Random Target to Search : 239932
----Linear Search----
Value Found at ARRAY[251273]location
Time Taken in Linear Search (NanoSeconds) : 9296610
----Binary Search----
Value Found at ARRAY[251273] location
Time Taken in Binary Search (NanoSeconds): 10964960
Random Target to Search : 91731
----Linear Search----
Value Not Found in ARRAY
Time Taken in Linear Search (NanoSeconds) : 7864321
----Binary Search----
Value Found at ARRAY[-1] location
Time Taken in Binary Search (NanoSeconds): 7760977
Random Target to Search : 725661
----Linear Search----
Value Not Found in ARRAY
Time Taken in Linear Search (NanoSeconds) : 7960585
----Binary Search----
Value Found at ARRAY[-1] location
Time Taken in Binary Search (NanoSeconds): 6239856
Random Target to Search : 738268
----Linear Search----
Value Found at ARRAY[773603]location
Value Found at ARRAY[773604]location
Time Taken in Linear Search (NanoSeconds) : 15369065
----Binary Search----
Value Found at ARRAY[773603] location
Time Taken in Binary Search (NanoSeconds): 6014059
Random Target to Search : 41921
----Linear Search----
Value Not Found in ARRAY
Time Taken in Linear Search (NanoSeconds) : 8916861
----Binary Search----
Value Found at ARRAY[-1] location
Time Taken in Binary Search (NanoSeconds): 5595025
Random Target to Search : 759789
----Linear Search----
Value Found at ARRAY[797334]location
Value Found at ARRAY[797335]location
Value Found at ARRAY[797336]location
Time Taken in Linear Search (NanoSeconds) : 17717637
----Binary Search----
Value Found at ARRAY[797335] location
Time Taken in Binary Search (NanoSeconds): 5988577
Random Target to Search : 428660
----Linear Search----
Value Found at ARRAY[449752]location
Value Found at ARRAY[449753]location
Time Taken in Linear Search (NanoSeconds) : 10265980
----Binary Search----
Value Found at ARRAY[449753] location
Time Taken in Binary Search (NanoSeconds): 5603873
Random Target to Search : 912626
----Linear Search----
Value Found at ARRAY[957304]location
Time Taken in Linear Search (NanoSeconds) : 6841863
----Binary Search----
Value Found at ARRAY[957304] location
Time Taken in Binary Search (NanoSeconds): 5941506
Random Target to Search : 394736
----Linear Search----
Value Found at ARRAY[413186]location
Time Taken in Linear Search (NanoSeconds) : 13359188
----Binary Search----
Value Found at ARRAY[413186] location
Time Taken in Binary Search (NanoSeconds): 278884
Random Target to Search : 716953
----Linear Search----
Value Found at ARRAY[752326]location
Time Taken in Linear Search (NanoSeconds) : 2695408
----Binary Search----
Value Found at ARRAY[752326] location
Time Taken in Binary Search (NanoSeconds): 431421
Random Target to Search : 97707
----Linear Search----
Value Not Found in ARRAY
Time Taken in Linear Search (NanoSeconds) : 2666388
----Binary Search----
Value Found at ARRAY[-1] location
Time Taken in Binary Search (NanoSeconds): 549275
