Assume the existence of a Widget class that implements the Comparable interface
ID: 3726311 • Letter: A
Question
Assume the existence of a Widget class that implements the Comparable interface and thus has a compareTo method that accepts an Object parameter and returns an int. Write an efficient static method, getWidgetMatch, that has two parameters. The first parameter is a reference to a Widget object. The second parameter is a potentially very large array of Widget objects that has been sorted in ascending order based on the Widget compareTo method. The getWidgetMatch searches for an element in the array that matches the first parameter on the basis of the equals method and returns true if found and false otherwise.
Explanation / Answer
public static boolean getWidgetMatch(Widget obj, Widget[] arr) {
int index = binarySearch(arr, obj);
if(index == -1)
return false;
else
return true;
}
// Returns index of x if it is present in arr[],
// else return -1
public static int binarySearch(Widget arr[], Widget x)
{
int l = 0, r = arr.length - 1;
while (l <= r)
{
int m = l + (r-l)/2;
// Check if x is present at mid
if (arr[m].compareTo(x) == 0)
return m;
// If x greater, ignore left half
if (arr[m].compareTo(x) < 0)
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
return -1;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.