Question

Use the definition shown below for the "jumpSearch" method of the SkipSearch class.
Notice that the method is delcared static. Therefore, you do not need to create a new 
instance of the object before the method is called. Simply use "SkipSearch.jumpSearch(...)"
with the appropriate 4 parameter values.

When objects are compared, you should use the "compareTo" method as in the following example.


item.compareTo(array[k])

When an object does not occur in an array, a sequential search for it must examine the entire array. If the array is sorted, you can improve the search by using the approach describedin Exercise 2. A jump search is an attempt to reduce the number of comparisons even further. Instead of examining the n objects in the array a sequentially, you look at the elements a[J, a[21, al3/), and so on, for some positive j> n. If the target t is less than one of these objects, you need to search only the portion of the array between the current object and the previous object. For example, if t is less than a[3j but is greater than a[2j, you search the elements a[2j+1], a[2j + 2], . . . , a[3j- l] by using the method in Exercise 2. Wh k'Л. but (k + 1) *j < n? Devise an algorithm for performing a jump search. Then, using [vn] as the value of, implement the jump search at should you do when t> a



However, not every type of object implements the compareTo method of the Comparable interface.
This is resolved with the use of the syntax " T extends Comparable<? super T>" where "T"
represents the type of objects you want to compare. On the other hand, if you only need to use
one type of data object, then you could just define your data class to implement Comparable instead.

public class SkipSearch
{
    public static <T extends Comparable<? super T>> 
                     boolean jumpSearch( T[] array, int size, T item, int skip ) 
    {
        /*  Searches the first n objects in a sorted array for a given item.
        T      -  data type or class name for the objects in the array.
        array  -  An array of Comparable objects sorted into ascending order.
        size   -  Array size.
        item   -  The item sought.
        skip   -  An integer > 0; The gap between examined items.
        returns  true if the item was found, or false if not. */


        // Insert your code here. Also define the main test class in a separate Java file.

    }
}

Answer 1

public class SkipSearch // you have to save your file with this name only

{

   public static <T extends Comparable<? super T>>

   boolean jumpSearch( T[] array, int size, T item, int skip )            // function used for searching

   {

      for(int i=0; i<size; i=i+skip) {                          // loop for comparing each value in array

           if(array[i].compareTo(item) == 0)                     // if if finds the value , it returns it

               return true;

       }

    

       return false;

   }

}