Need help with this Java project implementing an interpolation search, bolded the missing parts: /** ...
Need help with this Java project implementing an interpolation search, bolded the missing parts:
/**
A class that implements an interpolation search
and
a binary search of a sorted array of integers.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public class SearchComparer
{
private int[] a;
private int interpolationSearchCounter;
private int binarySearchCounter;
private static final int CAPACITY = 50;
public SearchComparer(int[] array, int n)
{
a = new int[CAPACITY];
for (int i = 0; i < n;
i++)
a[i] =
array[i];
resetCounters();
} // end default constructor
/** Resets the counters for each type of search.
*/
public final void resetCounters()
{
interpolationSearchCounter =
0;
binarySearchCounter = 0;
} // end resetCounters
/** Returns the number of searches used during an
interpolation search.
@return The number of searches used
during an interpolation search. */
public int getInterpolationSearchCount()
{
return
interpolationSearchCounter;
} // end getInterpolationSearchCount
/** Returns the number of searches used during a
binary search.
@return The number of searches used
during a binary search. */
public int getBinarySearchCount()
{
return binarySearchCounter;
} // end getBinarySearchCount
/** Searches a portion of a sorted array of
integers for a given value.
@param a
An array of integers sorted
into ascending order.
@param first
The integer index of the first array
element;
first >= 0 and < a.length
@param last
The integer index of the last
array element;
last - first >= 1; last < a.length
@param desiredItem The item
sought.
@return True if the item is found,
or false if not. */
public boolean interpolationSearch(int first, int
last, int desiredItem)
{
// ==== COMPLETE THIS METHOD
====
} // end interpolationSearch
/** Searches a portion of a sorted array of
integers for a given value.
@param a
An array of integers sorted
into ascending order.
@param first
The integer index of the first array
element;
first >= 0 and < a.length
@param last
The integer index of the last
array element;
last - first >= 1; last < a.length
@param desiredItem The item
sought.
@return True if the item is found,
or false if not. */
public boolean binarySearch(int first, int last, int
desiredItem)
{
// ==== COMPLETE THIS METHOD
====
} // end binarySearch
//
...................................................................
// Performs an interpolation search
private static void
doInterpolationSearch(SearchComparer searcher, int first,
int last, int
desiredItem, boolean willFind)
{
boolean result =
searcher.interpolationSearch(first, last, desiredItem);
System.out.print("Interpolation
search:\t");
giveMessage(desiredItem, result,
willFind);
} // end doInterpolationSearch
// Performs a binary search
private static void doBinarySearch(SearchComparer
searcher, int first, int last,
int desiredItem,
boolean willFind)
{
boolean result =
searcher.binarySearch(first, last, desiredItem);
System.out.print("Binary
search:\t\t");
giveMessage(desiredItem, result,
willFind);
} // end doBinarySearch
// Gives a message to the user as to whether the
item was found or not, and
// which outcome was expected.
private static void giveMessage(int desiredItem,
boolean result, boolean willFind)
{
if (result)
{
if
(willFind)
System.out.println("PASSES: " + desiredItem + "
was found");
else
System.out.println("FAILS: " + desiredItem + "
was not found");
} // end if
else
{
if
(willFind)
System.out.println("FAILS: " + desiredItem + "
was found");
else
System.out.println("PASSES: " + desiredItem + "
was not found");
} // end else
} // end giveMessage
// Displays the elements in the array
private static void displayArray(int[] array)
{
// ==== COMPLETE THIS METHOD
====
} // end displayArray
// Displays the counts for each type of search and
resets them.
private static void
displayAndResetCounts(SearchComparer searcher)
{
// ==== COMPLETE THIS METHOD
====
} // end displayAndResetCounts
public static void main(String[] args)
{
int a[] = {-10, -5, 1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11, 12,
13, 14, 15, 16, 20, 34, 99, 100, 200,
10000};
int b[] = {-6, -4, -2, 0, 2, 4,
6, 8, 10, 12, 14, 16, 18, 20,
22, 24, 26, 28, 30, 32, 34, 36, 38, 40};
SearchComparer searcher = new
SearchComparer(a, a.length);
System.out.println("Searching the
array");
displayArray(a);
doInterpolationSearch(searcher,
0, a.length - 1, 14, true);
doBinarySearch(searcher, 0,
a.length - 1, 14, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, -10, true);
doBinarySearch(searcher, 0,
a.length - 1, -10, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 10000, true);
doBinarySearch(searcher, 0,
a.length - 1, 10000, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 200, true);
doBinarySearch(searcher, 0,
a.length - 1, 200, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 23456, false);
doBinarySearch(searcher, 0,
a.length - 1, 23456, false);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, -6, false);
doBinarySearch(searcher, 0,
a.length - 1, -6, false);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 35, false);
doBinarySearch(searcher, 0,
a.length - 1, 35, false);
displayAndResetCounts(searcher);
//
...............................
searcher = new SearchComparer(b,
b.length);
System.out.println("Searching the
uniformly distributed array");
displayArray(b);
doInterpolationSearch(searcher,
0, a.length - 1, 24, true);
doBinarySearch(searcher, 0,
a.length - 1, 24, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, -6, true);
doBinarySearch(searcher, 0,
a.length - 1, -6, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 40, true);
doBinarySearch(searcher, 0,
a.length - 1, 40, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 38, true);
doBinarySearch(searcher, 0,
a.length - 1, 38, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 23456, false);
doBinarySearch(searcher, 0,
a.length - 1, 23456, false);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, -5, false);
doBinarySearch(searcher, 0,
a.length - 1, -5, false);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 33, false);
doBinarySearch(searcher, 0,
a.length - 1, 33, false);
displayAndResetCounts(searcher);
} // end main
} // end SearchComparer
Homework Answers
If you have any problem with the code feel free to comment.
Program
public class Test {
private int[] a;
private int interpolationSearchCounter;
private int binarySearchCounter;
private static final int CAPACITY = 50;
public Test(int[] array, int n) {
a = new int[CAPACITY];
for (int i = 0; i < n;
i++)
a[i] =
array[i];
resetCounters();
} // end default constructor
/** Resets the counters for each type of search.
*/
public final void resetCounters() {
interpolationSearchCounter =
0;
binarySearchCounter = 0;
} // end resetCounters
/**
* Returns the number of searches used during an
interpolation search.
*
* @return The number of searches used during an
interpolation search.
*/
public int getInterpolationSearchCount() {
return
interpolationSearchCounter;
} // end getInterpolationSearchCount
/**
* Returns the number of searches used during a binary
search.
*
* @return The number of searches used during a binary
search.
*/
public int getBinarySearchCount() {
return binarySearchCounter;
} // end getBinarySearchCount
/**
* Searches a portion of a sorted array of integers for
a given value.
*
* @param a An array of integers sorted into ascending
order.
* @param first The integer index of the first array
element; first >= 0
* and < a.length
* @param last The integer index of the last array
element; last - first
* >= 1; last < a.length
* @param desiredItem The item sought.
* @return True if the item is found, or false if
not.
*/
public boolean interpolationSearch(int first, int
last, int desiredItem) {
// ==== COMPLETE THIS METHOD
====
//loop condition
while (first <= last &&
desiredItem >= a[first] && desiredItem <= a[last])
{
interpolationSearchCounter++;//counting seraches
if (first ==
last) {//when itemisint first index
if (a[first] == desiredItem)
return true;
return false;
}
//calculating
position of the item
int pos = first
+ (((last - first) / (a[last] - a[first])) * (desiredItem -
a[first]));
if (a[pos] ==
desiredItem)//when i tem is present in the position
return true;
if (a[pos] <
desiredItem)
first = pos + 1;
else
last = pos - 1;
}
return false;
} // end interpolationSearch
/**
* Searches a portion of a sorted array of integers for
a given value.
*
* @param a An array of integers sorted into ascending
order.
* @param first The integer index of the first array
element; first >= 0
* and < a.length
* @param last The integer index of the last array
element; last - first
* >= 1; last < a.length
* @param desiredItem The item sought.
* @return True if the item is found, or false if
not.
*/
public boolean binarySearch(int first, int last, int
desiredItem) {
// ==== COMPLETE THIS METHOD
====
while(first <= last) {
binarySearchCounter++;//increasing the BinarySearchCount
int middleIndex
= (last+first)/2;//calculating middle index
//seraching for
item
if(desiredItem
< a[middleIndex])
last = middleIndex-1;
else
if(desiredItem > a[middleIndex])
first = middleIndex+1;
else
return true;
}
return false;
} // end binarySearch
// ...................................................................
// Performs an interpolation search
private static void doInterpolationSearch(Test
searcher, int first, int last, int desiredItem, boolean willFind)
{
boolean result =
searcher.interpolationSearch(first, last, desiredItem);
System.out.print("Interpolation
search:\t");
giveMessage(desiredItem, result,
willFind);
} // end doInterpolationSearch
// Performs a binary search
private static void doBinarySearch(Test searcher, int
first, int last, int desiredItem, boolean willFind) {
boolean result =
searcher.binarySearch(first, last, desiredItem);
System.out.print("Binary
search:\t\t");
giveMessage(desiredItem, result,
willFind);
} // end doBinarySearch
// Gives a message to the user as to whether the
item was found or not, and
// which outcome was expected.
private static void giveMessage(int desiredItem,
boolean result, boolean willFind) {
if (result) {
if
(willFind)
System.out.println("PASSES: " + desiredItem + "
was found");
else
System.out.println("FAILS: " + desiredItem + "
was not found");
} // end if
else {
if
(willFind)
System.out.println("FAILS: " + desiredItem + "
was found");
else
System.out.println("PASSES: " + desiredItem + "
was not found");
} // end else
} // end giveMessage
// Displays the elements in the array
private static void displayArray(int[] array) {
// ==== COMPLETE THIS METHOD
====
for(int i: array) {
System.out.print(i+" ");
}
System.out.println();
} // end displayArray
// Displays the counts for each type of search and
resets them.
private static void displayAndResetCounts(Test
searcher) {
// ==== COMPLETE THIS METHOD
====
System.out.println("Interpolation
Search Counter: "+searcher.getInterpolationSearchCount());
System.out.println("Binary Search
Counter: "+searcher.getBinarySearchCount());
searcher.resetCounters();
} // end displayAndResetCounts
public static void main(String[] args) {
int a[] = { -10, -5, 1, 2, 3, 4, 5,
6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 20, 34, 99, 100, 200, 10000
};
int b[] = { -6, -4, -2, 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40 };
Test searcher = new Test(a,
a.length);
System.out.println("Searching the
array");
displayArray(a);
doInterpolationSearch(searcher,
0, a.length - 1, 14, true);
doBinarySearch(searcher, 0,
a.length - 1, 14, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, -10, true);
doBinarySearch(searcher, 0,
a.length - 1, -10, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 10000, true);
doBinarySearch(searcher, 0,
a.length - 1, 10000, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 200, true);
doBinarySearch(searcher, 0,
a.length - 1, 200, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 23456, false);
doBinarySearch(searcher, 0,
a.length - 1, 23456, false);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, -6, false);
doBinarySearch(searcher, 0,
a.length - 1, -6, false);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 35, false);
doBinarySearch(searcher, 0,
a.length - 1, 35, false);
displayAndResetCounts(searcher);
// ...............................
searcher = new Test(b,
b.length);
System.out.println("Searching the
uniformly distributed array");
displayArray(b);
doInterpolationSearch(searcher,
0, a.length - 1, 24, true);
doBinarySearch(searcher, 0,
a.length - 1, 24, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, -6, true);
doBinarySearch(searcher, 0,
a.length - 1, -6, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 40, true);
doBinarySearch(searcher, 0,
a.length - 1, 40, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 38, true);
doBinarySearch(searcher, 0,
a.length - 1, 38, true);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 23456, false);
doBinarySearch(searcher, 0,
a.length - 1, 23456, false);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, -5, false);
doBinarySearch(searcher, 0,
a.length - 1, -5, false);
displayAndResetCounts(searcher);
doInterpolationSearch(searcher,
0, a.length - 1, 33, false);
doBinarySearch(searcher, 0,
a.length - 1, 33, false);
displayAndResetCounts(searcher);
} // end main
} // end SearchCompare
Output
![<terminated Test (1) [Java Application] C:\Program Files\ava\jre1.8.0_211\bin\javaw.exe (22-Nov-2019, 10:56:45 am) Searching](http://img.homeworklib.com/questions/7d813b70-8865-11ec-ac77-59e5c32cfe99.png?x-oss-process=image/resize,w_560)
Add Answer to:
Need help with this Java project implementing an
interpolation search, bolded the missing parts:
/**
...
I am currently using eclipse to write in java. A snapshot of the output would be...
I am currently using eclipse to write in java.
A snapshot of the output would be greatly appreciated to verify
that the program is indeed working. Thanks in advance for both your
time and effort.
Here is the previous exercise code:
/////////////////////////////////////////////////////Main
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
import java.util.*;
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in...
must provide the following public interface: public static void insertSort(int [] arr); public static void selectSort(int...
must provide the following public interface: public static void insertSort(int [] arr); public static void selectSort(int [] arr); public static void quickSort(int [] arr); public static void mergeSort(int [] arr); The quick sort and merge sort must be implemented by using recursive thinking. So the students may provide the following private static methods: //merge method //merge two sorted portions of given array arr, namely, from start to middle //and from middle + 1 to end into one sorted portion, namely,...
#2Trace These JAVA searches by hand on the following dataset. Sorted Data Set: 3, 5, 8,...
#2Trace These JAVA searches by hand on the following dataset. Sorted Data Set: 3, 5, 8, 9, 12, 14, 18, 19, 21, 23, 24, 26 #Trace the sorted data set using a binary search. Search target: 23 #Trace the sorted data set using a binary search. Search target: 15 (To trace a binary search, list the value of first, last, and mid for each pass through the method.) Use this method: private static <T extends Comparable<? super T>> boolean...
USE JAVA PROGRAMMING Create a program that would collect list of persons using double link list...
USE JAVA PROGRAMMING Create a program that would collect list of persons using double link list and use a Merge Sort to sort the object by age. Create a class called Person : name and age Create methods that add, and delete Person from the link list Create a method that sorts the persons' objects by age. package mergesort; public class MergeSortExample { private static Comparable[] aux; // auxiliary array for merges public static void sort(Comparable[] a) { aux =...
C++ Time the sequential search and the binary search methods several times each for randomly generated...
C++ Time the sequential search and the binary search methods several times each for randomly generated values, then record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment. Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? Both the table and your conclusions should...
Need help with this Java. I need help with the "to do" sections. Theres two parts...
Need help with this Java. I need help with the "to do" sections.
Theres two parts to this and I added the photos with the entire
question
Lab14 Part 1:
1) change the XXX to a number in the list, and YYY to a
number
// not in the list
2.code a call to linearSearch with the item number
(XXX)
// that is in the list; store the return in the variable
result
3. change both XXX numbers to the...
Java The following questions ask about tracing a binary search. To trace the binary search, list...
Java The following questions ask about tracing a binary search. To trace the binary search, list the value of first, last, and mid for each pass through the loop or method. Use one of these methods for your trace. public static int binarySearchIterative(int[] numbers, int target) { boolean found = false; int first = 0; int last = numbers.length - 1; while (first <= last && !found) { int mid = (first + last) / 2; if (numbers[mid] == target)...
JAVA programming 9.9 Ch 9, Part 2: ArrayList Searching import java.util.ArrayList; public class ArrayListSet { ...
JAVA programming 9.9 Ch 9, Part 2: ArrayList Searching import java.util.ArrayList; public class ArrayListSet { /** * Searches through the ArrayList arr, from the first index to the last, returning an ArrayList * containing all the indexes of Strings in arr that match String s. For this method, two Strings, * p and q, match when p.equals(q) returns true or if both of the compared references are null. * * @param s The string...
I have the following classes SearchMain.java import java.security.SecureRandom; import java.util.Arrays; import java.util.HashSet; import java.util.Set; /** *...
I have the following classes SearchMain.java import java.security.SecureRandom; import java.util.Arrays; import java.util.HashSet; import java.util.Set; /** * * DO NOT CHANGE THIS CODE * */ public class SearchMain { public static void main(String[] args) { ArraySearcher arraySearch = new ArraySearchImp(); SecureRandom secureRandom = new SecureRandom(); int[] sortedArray = generateRandomSortedIntArray(10); System.out.println(Arrays.toString(sortedArray)); Set<Integer> intSet = new HashSet<Integer>(); for(int i = 0; i < 5; i++) { ...
need help editing or rewriting java code, I have this program running that creates random numbers...
need help editing or rewriting java code, I have this program
running that creates random numbers and finds min, max, median ect.
from a group of numbers,array. I need to use a data class and a
constructor to run the code instead of how I have it written right
now. this is an example of what i'm being asked
for.
This is my code:
import java.util.Random;
import java.util.Scanner;
public class RandomArray {
// method to find the minimum number in...
I am currently using eclipse to write in java.
A snapshot of the output would be greatly appreciated to verify
that the program is indeed working. Thanks in advance for both your
time and effort.
Here is the previous exercise code:
/////////////////////////////////////////////////////Main
/*******************************************
* Week 5 lab - exercise 1 and exercise 2: *
* ArrayList class with search algorithms *
********************************************/
import java.util.*;
/**
* Class to test sequential search, sorted search, and binary search
algorithms
* implemented in...
Need help with this Java. I need help with the "to do" sections.
Theres two parts to this and I added the photos with the entire
question
Lab14 Part 1:
1) change the XXX to a number in the list, and YYY to a
number
// not in the list
2.code a call to linearSearch with the item number
(XXX)
// that is in the list; store the return in the variable
result
3. change both XXX numbers to the...
need help editing or rewriting java code, I have this program
running that creates random numbers and finds min, max, median ect.
from a group of numbers,array. I need to use a data class and a
constructor to run the code instead of how I have it written right
now. this is an example of what i'm being asked
for.
This is my code:
import java.util.Random;
import java.util.Scanner;
public class RandomArray {
// method to find the minimum number in...
Most questions answered within 3 hours.
-
The Yankee's have a contract with their newly hired manager that
requires a lump sum payment...
asked 16 minutes ago -
A travelling salesman sells milkshake mixing machines and on
average sells 8.9 machines per month. He...
asked 21 minutes ago -
what's the danger in the fact that the market value of a stock
is based on...
asked 36 minutes ago -
Describe how do you feel about the post below and
why?
Listening to the podcast reaffirmed...
asked 44 minutes ago -
To start an avalanche on a mountain slope, an artillery shell is
fired with an initial...
asked 57 minutes ago -
The population of bacteria in a culture can be modeled by P left
parenthesis t right...
asked 1 hour ago -
Which factors can prevent permanent fixation of an allele (i.e.
maintain genetic diversity)? Hint: You're going...
asked 1 hour ago -
Compare a two-year bond with two successive one-year bonds in a
situation in which an investor...
asked 1 hour ago -
Chapter 6
Search the internet and find a newspaper example of a price
ceiling, price floor...
asked 1 hour ago -
Sarah Bates, calendar year taxpayer, started a new business on
October 8th. A number of start-up...
asked 1 hour ago -
You and your friends are playing in the swimming pool with a
40-cm-diameter beach ball. How...
asked 1 hour ago -
Patterson Development sometimes sells property on an installment
basis. In those cases, Patterson reports income in...
asked 1 hour ago