Let\'s discuss it- it\'s a recursive function and it returns a boolean value. An
ID: 3594286 • Letter: L
Question
Let's discuss it- it's a recursive function and it returns a boolean value. And, then let's incorporate it in our ListArrayMain program Homework: to test it. 1. Set up an array of 100000000 (one hundred million!!) random integers and search for an integer and time it to find out how long it takes to find it. Compare the binary search time with the linear search time. Do this several times to see if binary search is really faster. ON Binary and Linear search. Write ON PAPER another binary search method - say, binarySearch2, which returns the actual cell number where the item is found-or returns -1 if it's not found 2. Hand it in at the next classExplanation / Answer
(1)
---------------------------------------------------------------------------------------------------------------------------------
public class CompareSearchingTechniques{
public static int recursiveBinarySearch(long[] sortedArray, int start, int end, long searchKey) {
if (start < end) {
int mid = start + (end - start) / 2;
if (searchKey < sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, start, mid, searchKey);
} else if (searchKey > sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, mid+1, end , searchKey);
} else {
return mid;
}
}
return -(start + 1);
}
public static int linearSearch(long[] inputArray, long searchKey){
int size = inputArray.length;
for(int i=0; i < size; i++){
if(inputArray[i] == searchKey){
return i;
}
}
return -1;
}
public static void main(String[] args) {
long searchKey = 354;
long[] inputArray = {43, 87,354, 415, 565, 787, 876, 989, 1453, 9898};
long startTime = System.nanoTime();
int indexLS = linearSearch(inputArray, searchKey);
long totalTimeForLinearSearch = System.nanoTime() - startTime;
System.out.println("totalTimeForLinearSearch: " + totalTimeForLinearSearch);
if (indexLS >= 0)
System.out.println("Linear Search: Key " + searchKey + " found at index: " + indexLS);
else
System.out.println("Linear Search: Element not found");
startTime = System.nanoTime();
int indexBS = recursiveBinarySearch(inputArray, 0, inputArray.length,searchKey);
long totalTimeForBinarySearch = System.nanoTime() - startTime;
System.out.println("totalTimeForBinarySearch: " + totalTimeForBinarySearch);
if (indexBS >= 0)
System.out.println("Binary Search: Key " + searchKey + " found at index: " + indexBS);
else
System.out.println("Binary Search: Element not found");
if(totalTimeForBinarySearch > totalTimeForLinearSearch)
System.out.println(" Binary Search takes more time than Linear Search");
else if (totalTimeForLinearSearch > totalTimeForBinarySearch)
System.out.println("Linear Search takes more time than Binary Search");
else
System.out.println("Searching times are equal.");
}
}
(2)
-------------------------------------------------------------------------------------------------------------------------------------------------
public class BinarySearch2 {
public static int recursiveBinarySearch(long[] sortedArray, int start, int end, long key) {
if (start < end) {
int mid = start + (end - start) / 2;
if (key < sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, start, mid, key);
} else if (key > sortedArray[mid]) {
return recursiveBinarySearch(sortedArray, mid+1, end , key);
} else {
return mid;
}
}
return -(start + 1);
}
public static void main(String[] args) {
long searchKey = 87;
long[] inputArray = {43, 87, 354, 415, 565, 787, 876, 989, 1453, 9898};
int index = recursiveBinarySearch(inputArray, 0, inputArray.length, searchKey);
if (index >= 0)
System.out.println("Binary Search: Key " + searchKey + " found at index: " + index);
else
System.out.println("Element not found");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.