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 eciently.

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 le. Your rst task is to read the input le 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 ecient 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 le name and output le name.
2. The input le 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 le 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.

Explanation / Answer

Answer.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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