Objectives: Compare search algorithms. Write programs with performance counters
ID: 3822799 • Letter: O
Question
Objectives:
Compare search algorithms.
Write programs with performance counters and statistical reporting.
Use file input in Java.
The program does not however use random number generation, which will be incorporated in a later assignment.
Correctly and completely implement the program for Linear Search and Binary Search for a B; add Interpolation Search for an A.
The program
The program should compare the efficiency of linear search, binary search and interpolation search by simulation.
The searches work in a sorted array of SIZE integers (more-or-less uniformly distributed) with values from 0 to TOP. The program runs searches for SEARCH integers in the range [0, TOP], half of which occur in the array. Keep counters for each search method, one for the number of probes for successful searches and one for the number of probes for unsuccessful searches.
Input:
File of SIZE integers with values in [0, TOP], in increasing order
File of SEARCH integers from [0, TOP], half in the array, and half not.
Static information:
Use integer constants for SIZE, TOP and SEARCH. Set SIZE = 100, TOP = 9999, SEARCH = 20.
Part 1:
Read in the array from a file.
Check each entry for lying in the range. Also, except for the first entry, check that each entry is larger than the previous. If either fails, print an error message, and terminate the program.
Set counters successCount, failCount, linearSuccessProbes, linearFailProbes, binarySuccessProbes, binaryFailProbes, interpSuccessProbes, and interpFailProbes to 0.
Part 2:
In a loop, read the next integer from searchTarget file. Check the value for the range constraint. If it fails, skip to Part 3. (If the range constraint fails on the first search target, print an error message and exit.)
Set another counter currentProbes = 0. Run linear search, counting probes. If the search succeeds, increment successCount, and add currentProbes to linearSuccessProbes. If it fails, increment failCount, and add currentProbes to linearFailProbes. (You should not report a result for the search.)
Repeat with binary search and interpolation search, but do not increment successCount or failCount.
Part 3:
Report your results. Ordinarily this should involve SIZE trials, but might have fewer if the range criterion fails at some point. Your results should be presented as follows, ideally in a table (for a bit of extra credit).
Table output (numbers are placeholders):
Linear Binary Interp
Count Avg Avg Avg
Success 7 42.17 7.23 5.17.
Fail 7 38.22 8.45 6.22
Text output:
Searches: 7 successful, 7 unsuccessful
Linear Search Probe Average: 42.17 successful, 38.22 unsuccessful
Binary Search Probe Average: 7.23 successful, 8.45 unsuccessful
Interp Search Probe Average: 5.17 successful, 6.22 unsuccessful
Explanation / Answer
Answer:
import java.util.*;
class Binaryfind
{
public static void main(String args[])
{
int c, begin, end, between, n, find, input[];
Scanner in = new Scanner(System.in);
System.out.println("Enter number of elements");
n = in.nextInt();
input = new int[n];
System.out.println("Enter " + n + " integers");
for (c = 0; c < n; c++)
input[c] = in.nextInt();
System.out.println("Enter value to find");
find = in.nextInt();
begin = 0;
end = n - 1;
between = (begin + end)/2;
while( begin <= end )
{
if ( input[between] < find )
begin = between + 1;
else if ( input[between] == find )
{
System.out.println(find + " found at location " + (between + 1) + ".");
break;
}
else
end = between - 1;
between = (begin + end)/2;
}
if ( begin > end )
System.out.println(find + " is not present in the list. ");
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.