I\'ve been trying to understand this instruction but I don\'t get it. All what I

Question

I've been trying to understand this instruction but I don't get it. All what I know is, I'm suppose to write a
a binary search but before that I need to rank these data below first. I can write binary search code but I don't know what I'm doing that for. Below is the instruction:

Write a Java program that will read the two sequences and then the ranks. For each rank you should trace the binary
search (one line per “probe”) and then indicate which element of which sequence has the desired rank. The first line of the
input file will give m, n, and p where m is the number of elements in the first sequence, n is the number of elements in the
second sequence, and p is the number of ranks for which binary searches will be performed. The sequence elements will be in the range 0...999,999. The ranks will be in the range 1...m+n.

For a given rank, the corresponding element could be in either one of the two input sequences. If stored as suggested in
(1.), the following (symmetric) observations allow a binary search to be used:
a. If the corresponding element is at a[ i ], then there must be an index j such that all of the following hold:
1. i + j == rank,
2. a[ i ] > b[ j ], and
3. a[ i ] <= b[ j + 1 ]
b. If the corresponding element is at b[ j ], then there must be an index i such that all of the following hold:
1. i + j == rank,
2. a[ i ] <= b[ j ], and
3. a[ i + 1 ] > b[ j ]

Below is my dataFile.txt
Below are the data file input

-999999 0 -999999 0
1 2 0 1
1 3 1 6
1 4 2 8
1 5 3 9
2 7 4 10
5 12 4 11
6 14 5 13
8 17 6 15
8 18 7 16
9 22 8 19
999999 0 8 20
8 21
9 23
9 24
9 25
999999 0







import java.io.*;
import java.util.*;


public class Proj1Main
{
private static Scanner ins = new Scanner(System.in);

public static void main(String[ ] args)
{
String filename;

int bMaxNum = 17;
int aMaxNum = 12;

int[ ] intArray = new int[ aMaxNum ];
int[ ] bIntArray = new int[ bMaxNum ];
int[ ] aRanks = new int[ aMaxNum ];
int[ ] bRanks = new int[ bMaxNum ];

System.out.println("Enter the name of the input file: ");
filename = ins.next();
Scanner input = null;
try
{
input = new Scanner(new File(filename));
}
catch(FileNotFoundException FNFE)
{

System.err.printf("Could not find the input file %s ", filename);
System.exit(1);
}

int iArrayElemnts;
int aRankElemnts;
int jArrayElemnts;
int bRankElemnts;
String comment = input.nextLine( ); // to go to next line in input
int index, min = 0;
String emptyLine;
String inputstring;
for(index = 0; index < aMaxNum; index++)
{

iArrayElemnts = input.nextInt( ); //read all first sequence inputs
aRankElemnts = input.nextInt( ); //read all second sequence inputs
jArrayElemnts = input.nextInt( ); //read all third sequence inputs
bRankElemnts = input.nextInt( ); //read all fourth sequence inputs

intArray[ index ] = iArrayElemnts; //assign all first sequence inputs into intArray array
aRanks[ index ] = aRankElemnts; //assign all second sequence inputs into aRanks array
bIntArray[ index ] = jArrayElemnts; //assign all third sequence inputs into bIntArray array
bRanks[ index ] = bRankElemnts; //assign all fourth sequence inputs into bRanks array
min++;
}
String inputLine;
int max = index;
while((max < bMaxNum) && input.hasNext( ))
{
jArrayElemnts = input.nextInt( );
bRankElemnts = input.nextInt( );

bIntArray[ max ] = jArrayElemnts;
bRanks[ max ] = bRankElemnts;
max++;
}

ranksByMerge(intArray, aRanks, bIntArray, bRanks, min, max);
}

private static void ranksByMerge(int[ ] a, int[ ] aRank, int[ ] b, int[ ] bRank, int mMin, int nMax)
{

int i, j, k;

i = j = k = 1;
while(i < mMin && j < nMax)
if(a[ i ] <= b[ j ])
aRank[ i++ ] = k++;
else
bRank[ j++ ] = k++;
while(i < mMin)
aRank[ i++ ] = k++;
while(j < nMax)
bRank[ j++ ] = k++;

//for(int m=0; m<aRank.length; m++)
//System.out.println(aRank[ m ]);

//for(int m=0; m<bRank.length;m++)
//System.out.println(bRank[ m ]);

}
}

Explanation / Answer

You should do binary search because its going to help you to see the element sequence

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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