Book - Data Structures and Abstractions with Java (4th Edition) Chapter 18, Prob
ID: 3827653 • Letter: B
Question
Book - Data Structures and Abstractions with Java (4th Edition)
Chapter 18, Problem 4P. I need the code in Java.
Consider an array data of n numerical values in sorted order and a list of numerical target values. Your goal is to compute the smallest range of array indices that contains all of the target values. If a target value is smaller than data [0], the range should start with -1. If a target value than data [n-1], the range should end with n.
For example, given the array in figure 18-10 and the target values (8,2,9,17), the range is -1 to 5.
A. Devise an efficient algorithm that solves this problem.
B. If you have n data values in the array and m target values in the list, what is the Big Oh performance of your algorithm?
C. Implement and test your algorithm.
Figure 3. An array for project 4.
Array
5
8
10
13
15
20
22
26
Index
0
1
2
3
4
5
6
7
Array
5
8
10
13
15
20
22
26
Index
0
1
2
3
4
5
6
7
Explanation / Answer
Hi,
Please see beow the class and sampleoutput.
Please comment forany queries/feedbacks.
Thanks,
TargetRange.java
import java.util.Scanner;
public class TargetRange {
public static void main(String [] args){
int [] intArray = null;
int [] targetValuesArray = null;
Scanner scan = new Scanner(System.in);
int NoOfElemnets = 0;
int NoOfTargetValues = 0;
int rangeStart=0;
int rangeEnd =0;
//Raeding the no of elements from the user
System.out.println(" Please enter the no of elements : ");
NoOfElemnets = Integer.valueOf(scan.nextLine());
intArray = new int[NoOfElemnets];
//Reading the elemnets from the user in a loop
System.out.println("Plese enter the elements : ");
for(int i=0;i<NoOfElemnets;i++){
intArray[i] = Integer.valueOf(scan.nextLine());
}
System.out.println(NoOfElemnets+" elements in the array : ");
for(int i=0;i<NoOfElemnets;i++){
System.out.print(intArray[i]+ " ");
}
//Reading the no of target values from the user
System.out.println(" Please enter the no of target values : ");
NoOfTargetValues = Integer.valueOf(scan.nextLine());
targetValuesArray = new int[NoOfTargetValues];
//Reading the elemnets from the user in a loop
System.out.println("Plese enter the Target values : ");
for(int i=0;i<NoOfTargetValues;i++){
targetValuesArray[i] = Integer.valueOf(scan.nextLine());
}
System.out.println(NoOfTargetValues+" Target Values : ");
for(int i=0;i<NoOfTargetValues;i++){
System.out.print(targetValuesArray[i]+ " ");
}
//Finding the min and amx value in target values
int minTarget =targetValuesArray[0];
int maxTarget =targetValuesArray[0];
for(int i=0;i<NoOfTargetValues;i++){
if(targetValuesArray[i]<minTarget){
minTarget = targetValuesArray[i];
}
if(targetValuesArray[i] > maxTarget){
maxTarget = targetValuesArray[i];
}
}
//Check minTarget and maxTarget are present in the intArray
//If Present rangeStart and rangeEnd can be found
boolean startFound =false;
boolean endFound =false;
for(int i=0;i<NoOfElemnets;i++){
if(intArray[i] == minTarget){
rangeStart = i-1;
startFound = true;
}
if(intArray[i] == maxTarget){
rangeEnd = i+1;
endFound = true;
}
}
//If not Present rangeStart can be found
//by checking each elemnet in intArray
if(!startFound){
for(int i=0;i<NoOfElemnets;i++){
if(intArray[i] > minTarget){ //Find the next greater value's index-1
rangeStart = i-1;
startFound = true;
break;
}
}
}
//If not Present rangeEnd can be found
//by checking each elemnet in intArray
if(!endFound){
for(int i=NoOfElemnets-1;i>=0;i--){
if(intArray[i] < maxTarget){//Find the next lesser value's index+1
rangeEnd = i+1;
endFound = true;
break;
}
}
}
System.out.println(" Range of target values : ["+rangeStart+","+rangeEnd+"]");
}
}
Sample output:
Please enter the no of elements :
8
Plese enter the elements :
5
8
10
13
15
20
22
26
8 elements in the array :
5 8 10 13 15 20 22 26
Please enter the no of target values :
4
Plese enter the Target values :
8
2
9
17
4 Target Values :
8 2 9 17
Range of target values : [-1,5]