JAVA Implement and test a templated binary search. Note that your test program m

Question

JAVA

Implement and test a templated binary search. Note that your test program must use at least 2 types of data to prove that search is templated. Templating means that instead of passing a parameter such as Integer you pass a parameter T. (T is a type variable and can be named anything). This means that you can call bsearch with different types of objects. Pseudo Code Examples: Bsearch(String) Bsearch(lnteger) This means you do not have to write 2 separate bsearch methods, one for String and one for Integer. The heart of how this is accomplished is the Comparable interface. If a class implements Comparable, it defines less than, greater than and equals. Also, by making the type variable you can call with any object that implements Comparable. Example Code: public class Searches public static int bsearch (T [] a, int first, int last, T key) called in main as: result = Searches.bsearch(IntegerArray, 0, 10, key); result = Searchesbsearch(String Array, 0, 10, key); Example Outputs: Integer test array contains: 0 2 4 6 8 10 12 14 16 18 -3 is not in the array -2 is not in the array -1 is not in the array 0 is at index 0 1 is not in the array 2 is at index 1 3 is not in the array 4 is at index 2 String test array contains: apples oranges peaches strawberries watermelons apples is at index 0 plums |is not in the array Process completed

Explanation / Answer

//Test java program for the generic method bsearch
//Searches.java
public class Searches
{  
   public static void main(String[] args) {
      
      
       Integer[] IntegerArray={0,2,4,6,8,10,12,14,16,18};
       System.out.println("Integer test array contains : ");
       print(IntegerArray);
       int result;
              
       result=Searches.<Integer>bsearch(IntegerArray, 0, 10, -3);
       if(result==-1)
           System.out.println("-3 is not in the array");
      
       result=Searches.<Integer>bsearch(IntegerArray, 0, 10, -2);
       if(result==-1)
           System.out.println("-2 is not in the array");
      
       result=Searches.<Integer>bsearch(IntegerArray, 0, 10, -1);
       if(result==-1)
           System.out.println("-1 is not in the array");
      
       result=Searches.<Integer>bsearch(IntegerArray, 0, 10, 0);
       if(result!=-1)
           System.out.println("0 is at index "+result);
      
       result=Searches.<Integer>bsearch(IntegerArray, 0, 10, 1);
       if(result==-1)
           System.out.println("1 is not in the array ");
      
       result=Searches.<Integer>bsearch(IntegerArray, 0, 10, 2);
       if(result!=-1)
           System.out.println("2 is at index "+result);
      
       result=Searches.<Integer>bsearch(IntegerArray, 0, 10, 3);
       if(result!=-1)
           System.out.println("3 is at index "+result);
      
       result=Searches.<Integer>bsearch(IntegerArray, 0, 10, 4);
       if(result!=-1)
           System.out.println("4 is at index "+result);
      
      
       String[] StringArray={"apples","oranges","peaches",
               "strawberries","watermelons"};
      
       System.out.println("String test array contains");
       print(StringArray);
      
       result=Searches.<String>bsearch(StringArray, 0, 5, "apples");
       if(result!=-1)
           System.out.println("apples is at index "+result);
      
       result=Searches.<String>bsearch(StringArray, 0, 5, "plums");
       if(result==-1)
           System.out.println("plums is not in the array");
      
      
   }
  
   //helper method that prints the elements of array T
   public static <T> void print(T[] a)
   {
       for (int i = 0; i < a.length; i++)
       {
           System.out.print(a[i]+" ");
       }
      
       System.out.println();
   }
  
  
   /**
   * Template binarySearch
   * Input: generic array,T, first and last,key
   * Output : -1 if not found or returns index of element
   *
   * */
   public static <T extends Comparable<T>>
   int bsearch(T[] a, int first, int last,T key) {
          
       if (first < last) {
                int mid = first + (last - first) / 2;
                if (key.compareTo(a[mid])<0) {
                    return bsearch(a, first, mid, key);
                   
                } else if (key.compareTo(a[mid])>0) {
                    return bsearch(a, mid+1, last , key);
                   
                } else {
                    return mid;
                }
            }
            return -1;
       } // binarySearch  
}

Sample Output:

Integer test array contains :
0 2 4 6 8 10 12 14 16 18
-3 is not in the array
-2 is not in the array
-1 is not in the array
0 is at index 0
1 is not in the array
2 is at index 1
4 is at index 2
String test array contains
apples oranges peaches strawberries watermelons
apples is at index 0
plums is not in the array

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

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