Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Java code ranking of an element using linear search

Posted on 2010-09-22
3
Medium Priority
?
667 Views
Last Modified: 2013-11-23
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\n", 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 ]);

    }
}
0
Comment
Question by:cadrin16
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 2

Accepted Solution

by:
ttn_ earned 2000 total points
ID: 33901086
Lemme see if I can clarify for you.

It seems that the code you are given ranks both arrays for you based on the value in each array. As you can see, the data input file has four columns: the first column contains the values of array a, the second column contains the rank of each value, the third column contains the values of array b, and the last column contains the ranks of b.

From what I can tell, you are supposed to perform one binary search for every rank to determine the position of each value for both arrays. The rank is there to tell you in what order you are supposed to do each search. Hope this helps a bit.

-Tommy
0
 
LVL 53

Expert Comment

by:Dhaest
ID: 34134543
This question has been classified as abandoned and is being closed as part of the Cleanup Program.  See my comment at the end of the question for more details.
0

Featured Post

Build and deliver software with DevOps

A digital transformation requires faster time to market, shorter software development lifecycles, and the ability to adapt rapidly to changing customer demands. DevOps provides the solution.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

If you haven’t already, I encourage you to read the first article (http://www.experts-exchange.com/articles/18680/An-Introduction-to-R-Programming-and-R-Studio.html) in my series to gain a basic foundation of R and R Studio.  You will also find the …
In this post we will learn different types of Android Layout and some basics of an Android App.
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses

704 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question