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 described in 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[2j], a[3j], 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 - 1] by using the method in Exercise 2 on the textbook’s page 544. The implementation should take care of the case when t > a[k × j], but (k + 1) × j > n. Devise an algorithm for performing a jump search. Then, using ⌈√n⌉ as the value of j, implement the jump search. Add more test cases in the main method. Modify and save the file as JumpSearchYourlastname.java.

Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
icon
Related questions
Question

Searches – Directed Lab Work
1. 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 described in
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[2j], a[3j], 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 - 1] by using the method in Exercise 2 on the textbook’s page
544. The implementation should take care of the case when t > a[k × j], but (k + 1) × j > n.
Devise an algorithm for performing a jump search.
Then, using
⌈√n⌉
as the value of j, implement the jump search. Add more test cases in the main method.
Modify and save the file as JumpSearchYourlastname.java.
2. An interpolation search assumes that the data in an array is sorted and uniformly distributed.
Whereas a binary search always looks at the middle item in an array, an interpolation search
looks where the sought-for item is more likely to occur. For example, if you searched your
telephone book for Victoria Appleseed, you probably would look near its beginning rather
than its middle. And if you discovered many Appleseeds, you would look near the last
Appleseed. Instead of looking at the element a[mid] of an array a, as the binary search would,
an interpolation search examines a[index], where
 p = (desiredElement - a[first]) / (a[last] - a[first])
 index = first + [(last – first) × p]
Implement an interpolation search of an array. For particular arrays, compare the outcomes
of an interpolation search and of a binary search. Consider arrays that have uniformly
distributed entries and arrays that do not. Modify and save the file as
SearchComparerYourlastname.java. 

Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps

Blurred answer
Knowledge Booster
Quicksort
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-engineering and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY