Generic Binary Search: Modify the search method so it is a generic method. The m
ID: 3759019 • Letter: G
Question
Generic Binary Search: Modify the search method so it is a generic method. The method should use generic notation to accept an arrya ofany object that implement the Comparable interface.
import java.util.Arrays;
import java.util.Scanner;
public class ObjectBinarySearcher {
// TODO make this method a generic method
public static int search(Comparable[] array, Comparable value) {
int first; // First array element
int last; // Last array element
int middle; // Mid point of search
int position; // Position of search value
boolean found; // Flag
// Set the initial values.
first = 0;
last = array.length - 1;
position = -1;
found = false;
// Search for the value.
while (!found && first <= last) {
// Calculate mid point
middle = (first + last) / 2;
// If value is found at midpoint...
if (array[middle].compareTo(value) == 0) {
found = true;
position = middle;
}
// else if value is in lower half...
else if (array[middle].compareTo(value) > 0)
last = middle - 1;
// else if value is in upper half....
else
first = middle + 1;
}
// Return the position of the item, or -1
// if it was not found.
return position;
}
public static void main(String[] args) {
int result;
String searchValue;
String input;
// Create a String array with test values.
String[] values = {"Zeb", "Deb", "Will", "Karen",
"Aaron", "Chris", "Barb", "Kenny"};
// Create a Scanner object to read keyboard input.
Scanner keyboard = new Scanner(System.in);
Arrays.sort(values);
// Display the array's contents.
System.out.println("Array contents: ");
for (String element : values)
System.out.print(element + " ");
System.out.println();
do {
// Get a value to search for.
System.out.print("Enter a value to search for: ");
searchValue = keyboard.nextLine();
// Search for the value
result = ObjectBinarySearcher.search(values, searchValue);
// Display the results.
if (result == -1)
System.out.println(searchValue + " was not found.");
else {
System.out.println(searchValue + " was found at " +
"element " + result);
}
// Does the user want to search again?
System.out.print("Do you want to search again? (Y or N): ");
input = keyboard.nextLine();
} while (input.charAt(0) == 'y' || input.charAt(0) == 'Y');
}
}
Explanation / Answer
import java.util.Arrays;
import java.util.Scanner;
public class ObjectBinarySearcher<T extends Comparable<T>> {
// TODO make this method a generic method
public static <T> int search(T[] array, Comparable<T> value) {
int first; // First array element
int last; // Last array element
int middle; // Mid point of search
int position; // Position of search value
boolean found; // Flag
// Set the initial values.
first = 0;
last = array.length - 1;
position = -1;
found = false;
// Search for the value.
while (!found && first <= last) {
// Calculate mid point
middle = (first + last) / 2;
// If value is found at midpoint...
if (value.compareTo(array[middle]) == 0) {
found = true;
position = middle;
}
// else if value is in lower half...
else if (value.compareTo(array[middle]) < 0)
last = middle - 1;
// else if value is in upper half....
else
first = middle + 1;
}
// Return the position of the item, or -1
// if it was not found.
return position;
}
public static void main(String[] args) {
int result;
String searchValue;
String input;
// Create a String array with test values.
String[] values = { "Zeb", "Deb", "Will", "Karen", "Aaron", "Chris", "Barb", "Kenny" };
// Create a Scanner object to read keyboard input.
Scanner keyboard = new Scanner(System.in);
Arrays.sort(values);
// Display the array's contents.
System.out.println("Array contents: ");
for (String element : values)
System.out.print(element + " ");
System.out.println();
do {
// Get a value to search for.
System.out.print("Enter a value to search for: ");
searchValue = keyboard.nextLine();
// Search for the value
result = ObjectBinarySearcher.search(values, searchValue);
// Display the results.
if (result == -1)
System.out.println(searchValue + " was not found.");
else {
System.out.println(searchValue + " was found at " + "element " + result);
}
// Does the user want to search again?
System.out.print("Do you want to search again? (Y or N): ");
input = keyboard.nextLine();
} while (input.charAt(0) == 'y' || input.charAt(0) == 'Y');
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.