screenshot of the project from the textbook: When an object does not occur in an
ID: 3735556 • Letter: S
Question
screenshot of the project from the textbook:
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 aExplanation / Answer
Please find my implementaton:
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.
for(int i=0; i<size; i=i+skip) {
if(array[i].compareTo(item) == 0)
return true;
}
return false;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.