You are to write a program name search.java that will do the following: a. You a
ID: 3762336 • Letter: Y
Question
You are to write a program name search.java that will do the following: a. You are to create 3 arrays - prompt the user for a number that is greater than 100 that will serve as the size for the arrays (all 3 arrays will have the same user input size). Call them A, B & C. b. Generate this amount of random numbers to fill these arrays – the random numbers must range from 1 to 99. c. Write 1 sequential search voided function (method) name Seq_search() that accepts two parameters – 1 array and a target value to search for. Call this method 3 times (pass Array A as one of the paramters) once with a target value of 1, next with a target value of 50 and next with a target value of 100. Each time you call this method, you must invoke a clock to see how long it takes to execute and print out the time with an appropriate message. d. Write 1 binary search voided function (method) using Loop only, name Bin_search() that accepts two parameters – 1 array and a target value to search for. In the main program first sort array B and time it to see how long it took to sort. Now pass this sorted array as a parameter to this method calling it 3 times once with a target value of 1, next with a target value of 50 and next with a target value of 100. Each time you call this method, you must invoke a clock to see how long it takes to execute and add the time it took to sort the array to this time and print out the time with an appropriate message. e. Write 1 binary search voided function (method) that uses recursion only, name BinRe_search() that accepts two parameters – 1 array and a target value to search for. In the main program first sort array C and time it to see how long it took to sort. Now pass this sorted array as a parameter to this method calling it 3 times once with a target value of 1, next with a target value of 50 and next with a target value of 100. Each time you call this method, you must invoke a clock to see how long it takes to execute and add the time it took to sort the array to this time and print out the time with an appropriate message. f. After you get the time, give an analysis as to which you think is a better algorithm to use and under what circumstance it is better to be used.
Explanation / Answer
import java.util.Random;
import java.util.Scanner;
/**
* @author srinu class select optimum search
*/
public class Search {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
System.out.print("Please enter a number that is greater than 100 :");
long startTime, stopTime;
int size = scanner.nextInt();
int A[] = new int[size];
int B[] = new int[size];
int C[] = new int[size];
A = setArrayRandom(size);
B = setArrayRandom(size);
C = setArrayRandom(size);
System.out.println("Sequential Search :");
startTime = System.nanoTime();
Seq_search(A, 1);
stopTime = System.nanoTime();
System.out
.println("1. Time Taken For Sequential Search in nano seconds :"
+ (stopTime - startTime));
startTime = System.nanoTime();
Seq_search(A, 50);
stopTime = System.nanoTime();
System.out
.println("2. Time Taken For Sequential Search in nana seconds :"
+ (stopTime - startTime));
startTime = System.nanoTime();
Seq_search(A, 100);
stopTime = System.nanoTime();
System.out
.println("3. Time Taken For Sequential Search in nana seconds :"
+ (stopTime - startTime));
System.out.println("Binary Search :");
startTime = System.nanoTime();
Bin_search(sortArray(B,size), 1);
stopTime = System.nanoTime();
System.out
.println("1. Time Taken For Binary Search in nano seconds :"
+ (stopTime - startTime));
startTime = System.nanoTime();
Bin_search(sortArray(B,size), 50);
stopTime = System.nanoTime();
System.out
.println("2. Time Taken For Binary Search in nano seconds :"
+ (stopTime - startTime));
startTime = System.nanoTime();
Bin_search(sortArray(B,size), 100);
stopTime = System.nanoTime();
System.out
.println("3. Time Taken For Binary Search in nano seconds :"
+ (stopTime - startTime));
System.out.println("Recursive Binary Search :");
startTime = System.nanoTime();
BinRe_search(sortArray(B,size), 0,B.length,1);
stopTime = System.nanoTime();
System.out
.println("1. Time Taken For Recursive Binary Search in nano seconds :"
+ (stopTime - startTime));
startTime = System.nanoTime();
BinRe_search(sortArray(B,size), 0,B.length,50);
stopTime = System.nanoTime();
System.out
.println("2. Time Taken For Recursive Binary Search in nano seconds :"
+ (stopTime - startTime));
startTime = System.nanoTime();
BinRe_search(sortArray(B,size), 0,B.length,100);
stopTime = System.nanoTime();
System.out
.println("3. Time Taken For Recursive Binary Search in nano seconds :"
+ (stopTime - startTime));
}
/**
* @param sortedArray
* @param start
* @param end
* @param key
* @return
*/
public static int BinRe_search(int[] sortedArray, int start, int end, int key) {
if (start < end) {
int mid = start + (end - start) / 2;
if (key < sortedArray[mid]) {
return BinRe_search(sortedArray, start, mid, key);
} else if (key > sortedArray[mid]) {
return BinRe_search(sortedArray, mid+1, end , key);
} else {
return mid;
}
}
return -(start + 1);
}
/**
* @param arr
* @param search
* @return
*/
public static int Bin_search(int[] arr, int search) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (arr[mid] == search) {
return mid;
} else if (arr[mid] < search) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
/**
* @param numbers
* @param key
* @return
*/
public static int Seq_search(int[] numbers, int key) {
for (int index = 0; index < numbers.length; index++) {
if (numbers[index] == key) {
return index; // We found it!!!
}
}
// If we get to the end of the loop, a value has not yet
// been returned. We did not find the key in this array.
return -1;
}
/**
* @param nos
* @param n
* @return
*/
private static int[] sortArray(int nos[], int n) {
for (int i = 1; i < n; i++) {
int j = i;
int B = nos[i];
while ((j > 0) && (nos[j - 1] > B)) {
nos[j] = nos[j - 1];
j--;
}
nos[j] = B;
}
return nos;
}
/**
* @param arraySize
* @return
*/
public static int[] setArrayRandom(int arraySize) {
int min = 1, max = 99;
Random rand = new Random();
int array[] = new int[arraySize];
for (int i = 0; i < arraySize; i++) {
int randomNum = rand.nextInt((max - min) + 1) + min;
array[i] = randomNum;
}
return array;
}
}
output:
Please enter a number that is greater than 100 :103
Sequential Search :
1. Time Taken For Sequential Search in nano seconds :15822
2. Time Taken For Sequential Search in nana seconds :3421
3. Time Taken For Sequential Search in nana seconds :10691
Binary Search :
1. Time Taken For Binary Search in nano seconds :205687
2. Time Taken For Binary Search in nano seconds :27796
3. Time Taken For Binary Search in nano seconds :13256
Recursive Binary Search :
1. Time Taken For Recursive Binary Search in nano seconds :18388
2. Time Taken For Recursive Binary Search in nano seconds :14111
3. Time Taken For Recursive Binary Search in nano seconds :8125
Analysis and Observations :
1. Sequential Search
Sequential search has a average and worst-case runtime of O(N)
Sequential search is the simplest approach. Given a collection you try every
element in the collection until you have found the element or until you reach the
end of the collection.
Sequential Search is extremely easy to implement.
2. Binary Search
Binary search requires that the collection is already sorted
Binary search checks the element in the middle of the collection. If the search
element smaller or greater then the found element then a sub-array is defined which
is then search again. If the searched element is smaller then the found element
then
the sub-array is from the start of the array until the found element. If the
searched element is larger then the found element then the sub-array is from the
found element until the end of the array. Once the searched element is found or the
collection is empty then the search is over.
Binary search cuts the search space in each iteration into half and has therefore
O(lg N) runtime behavior.
3. Binary Recursive Search
A binary search or half-interval search algorithm finds the position of a
specified value (the input "key") within a sorted array. In each step, the
algorithm compares the input key value with the key value of the middle element of
the array. If the keys match, then a matching element has been found so its index,
or position, is returned. Otherwise, if the sought key is less than the middle
element's key, then the algorithm repeats its action on the sub-array to the left
of the middle element or, if the input key is greater, on the sub-array to the
right. If the remaining array to be searched is reduced to zero, then the key
cannot be found in the array and a special "Not found" indication is returned.
Every iteration eliminates half of the remaining possibilities. This makes binary
searches very efficient - even for large collections.
Binary search requires a sorted collection. Also, binary searching can only be
applied to a collection that allows random access (indexing).
Worst case performance: O(log n)
Best case performance: O(1)
Recursion is used in this algorithm because with each pass a new array is created
by cutting the old one in half. The binary search procedure is then called
recursively, this time on the new array. Typically the array's size is adjusted by
manipulating a beginning and ending index. The algorithm exhibits a logarithmic
order of growth because it essentially divides the problem domain in half with
each pass.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.