Assume the existence of a Widget class that implements the Comparable interface

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

We can use binary search for an efficient implementation of getWidgetMatch method since the Widget class implements Comparable method and has overriden compareTo method.

public static boolean getWidgetMatch(Widget widget, Widget[] widgetObjectArray)
{

   int start = 0;       //Initialize the start with first element of array
   int end = widgetObjectArray.length - 1;       //Initialize the start with last element of array
   while(start<=end)       //Traverse till start is not greater than end
   {
       int mid = (start + end) / 2;       //Compute mid as middle element of current section of the array
       if(widget.equals(widgetObjectArray[mid])) //If widget object is equal to mid object return true
           return true;
       if(widget.compareTo(widgetObjectArray[mid])<1)       //If widget object is less than mid object, make end point of search to mid -1
           end = mid - 1 ;
       else
           start = mid + 1;       //If widget object is greater than mid object, make start point of search to mid + 1

   }

   return false; //If widget object not found in the array return false
}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.