You are given an arbitrary input set of integers. Periodically you receive a que

Question

You are given an arbitrary input set of integers. Periodically you receive a query with an integer
x that wishes to know how many integers in the input set are less than or equal to x. Assume
that the number of such queries k is far greater than the number of integers n, so it is worthwhile
preprocessing the input set of integers to answer the queries efficiently.

For simplicity, we will assume that you are given the query integer x along with the input set of
integers together in the same input file. Your task is to read the input file to obtain the integer
x, and the input set of integers. Then place the n integers, n >= 1, into an array A[0; n ?? 1]. You
can then sort the integers in place using insertion sort. (Apply the InsertionSort(A[0..n-1])
algorithm from the Levitin text to sort the array for subsequent processing.)
Next develop an efficient approach to determine the number of input integers less than or equal
to the value x.

Briely outline your algorithm, including the step to compute the number of integers less than
or equal to the input value x. Analyze the asymptotic time complexity of the algorithm, assuming
there are n input integers and k queries with dierent values of x.

Implementation

You should implement your algorithm  Java programming.
1. Your program should accept a user specied input file name and output le name.
2. The input file will contain:
(a) integer x on the rst line,
(b) followed by a sequence of one or more integers, one integer per line.
1
3. The program should send output to the user specied output le name.
4. The output file should contain:
(a) The number of input integers less than or equal to x on the rst line,
(b) followed by the sorted sequence of input integers, one integer per line

Please comment ONLY answer to the question below.

Explanation / Answer

/* IMPORTANT: class must not be public. */

/* IMPORTANT: class must not be public. */

import java.io.BufferedReader;

import java.io.InputStreamReader;
import java.io.*;

class HelloWorld {

public static void main(String args[] ) throws Exception {

BufferedReader brreadname = new BufferedReader(new InputStreamReader(System.in));

System.out.print("enter file name to be searched ");

String line = brreadname.readLine();

BufferedReader br = new BufferedReader(new FileReader(new File(line)));

int target = Integer.parseInt(br.readLine());

int[] array = new int[1000];

int i=0;

// System.out.print("enter elements in the array ");

while((line = br.readLine())!=null){

array[i++]= Integer.parseInt(line);

}

insertionSort(array);

System.out.println("numbers which are less than or equal to "+ target + " are " +PrintIndicesForValue(array,target));

write("output.txt",array);

}

public static void insertionSort(int array[]) {

int n = array.length;

for (int j = 1; j < n; j++) {

int key = array[j];

int i = j-1;

while ( (i > -1) && ( array [i] > key ) ) {

array [i+1] = array [i];

i--;

}

array[i+1] = key;

}

}

public static void write (String filename, int[]x) throws IOException{
BufferedWriter outputWriter = null;
outputWriter = new BufferedWriter(new FileWriter(filename));
for (int i = 0; i < x.length; i++) {
// Maybe:
outputWriter.write(x[i]+"");
// Or:
outputWriter.write(Integer.toString(x[i]));
outputWriter.newLine();
}
outputWriter.flush();
outputWriter.close();
}

public static int PrintIndicesForValue(int[] numbers, int target) {

if (numbers == null)

return 0;

// get the end index of target number

int endIndex = -1;

int low = 0;

int high = numbers.length - 1;

while (low <= high) {

int mid = (high - low) / 2 + low;

if (numbers[mid] > target) {

high = mid - 1;

}

else if (numbers[mid] == target) {

endIndex = mid;

low = mid + 1;

}

else

low = mid + 1;

}

return endIndex+1;

}

}

I/P:

enter the element to be searched

4

enter the number of elements in the array

5

enter the elements in array

1

3

4

8

3

O/P:

numbers which are less than or equal to 4 are 4

the sorted array of numbers are

1

3

3

4

8

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.