Write a java program to use binary search that takes in a file containing UC stu

Question

Write a java program to use binary search that takes in a file containing UC

student records and another file containing Pierce College alumni records and writes out to a file all the Pierce College

alumni who are attending UC schools, ordered by ID.

You think about the problem for a minute and you come up with a plan.

- You will create a Student class representing student records. It will have three data members

corresponding to the data contained in the student records file

int id;

String name;

String school;

- You will have no setters or getters in your Student class.

- You will override the equals method to consider two student objects as equal if they have the same ID.

- You will implement the comparable interface to allow sorting of student objects by ID.

- You will override the toString method to print the fields as they appear in the student records file.

The idea is that for every record you read from the file, you will create a Student object. You will store

the UC students into a student array and the SMC alumni into another student array. Parts 2 and 3

operate on these arrays.

Part 2:

Now that you have two arrays with one containing UC students and the other containing SMC

alumni, you plan to process the arrays and find the students who belong to both arrays. Your data

structures are these two arrays. Your algorithm will be: for each student in the UC students array you

try to find it in the SMC students array by doing a linear search on the SMC students array (comparing

for equality). If you do find it, that UC student is then stored in an array containing students who are

SMC alumni attending UC schools. Once you have the array of the common students, it is sorted by ID

and printed to a file. We will use the Java library sort for this.

Part 3:

After running your program from Part 2 and discovering that it takes ~ 5 - 10 minutes to

complete for the given input (much longer for larger files), you decide to really think about the problem

in order to find a solution that does not force your boss to go get a cup of coffee every time she needs

to run your program. It seems even those powerful processors in today's computers can't really save a

bad algorithm.

You remember from class that binary search is much more efficient than linear search for

finding an element in an array and decide to try it out. We will use the Java library binary search for

this. Your algorithm will be: for each student in the UC array you will binary search the sorted SMC

array. If the binary search finds the student, that UC student is stored in an array containing students

who are SMC alumni attending UC schools. Once you have the array of the common students, it is

sorted by ID and printed to a file. We will use the Java library sort for this.

Explanation / Answer

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

class Student{
   int id;
   String name;
   String school;
   public Student(int i,String n,String s){
       id = i;
       name = n;
       school = s;
   }
}

class main{
   // Linear Search
   public static boolean lin_search(ArrayList<Student> ar,Student s){
       for (int i = 0; i < ar.size(); i++){
           if (s.id == ar.get(i).id) return true;
       }
       return false;
   }
  
   // Binary Search
   public static boolean bin_search(ArrayList<Student> ar,Student s){
       int start = 0;
int end = ar.size() - 1;
int mid;
while (start <= end) {
mid = (start + end) / 2;
if (s.id == ar.get(mid).id)   return true;
if (s.id < ar.get(mid).id) end = mid - 1;
else    start = mid + 1;
}
return false;
   }

   public static ArrayList<Student> sort(ArrayList<Student> ar){
       for (int i = 0; i < ar.size(); i++){
           for (int j = i+1; j < ar.size(); j++){
               Student s_1 = ar.get(i);
               Student s_2 = ar.get(j);
               if (s_1.id > s_2.id){
                   ar.set(i,s_2);
                   ar.set(j,s_1);
               }
           }
       }
   }
   public static void main(String[] args){
       Scanner sc = new Scanner(System.in);
       System.out.print("Enter the file containing UC student records : ");
       String file_1 = sc.nextLint();
       BufferedReader br = null;
       ArrayList<Student> ar_1 = new ArrayList<Student>();
       ArrayList<Student> ar_2 = new ArrayList<Student>();
       String[] res;
       int age;
       String name,school;
       Student st;
       try{
           String line;
           br = new BufferedReader(new FileReader(file_1));
           while ((line = br.readLine()) != null) {
               res = line.split(" ");
               age = Integer.parseInt(res[0]);
               name = res[1];
               school = res[2];
               st = new Student(age,name,school);
               ar_1.add(st);
           }
           ar_1 = sort(ar_1);
          
           System.out.print("Enter the file containing SMC student records : ");
           String file_2 = sc.nextLint();
           try{
               br = new BufferedReader(new FileReader(file_2));
               while ((line = br.readLine()) != null) {
                   res = line.split(" ");
                   age = Integer.parseInt(res[0]);
                   name = res[1];
                   school = res[2];
                   st = new Student(age,name,school);
                   ar_2.add(st);
               }
               ar_2 = sort(ar_2);
               /* Part 2 */
               System.out.println("Student in Both Array : ");
               for (int i = 0; i < ar_1.size(); i++){
                   st = ar_1.get(i);
                   if (lin_search(ar_2,st) == true)
                       System.out.println(st.id+ " "+st.name+" "+st.school);
               }

               /* Part 3 */
               System.out.println("Student in Both Array : ");
               for (int i = 0; i < ar_1.size(); i++){
                   st = ar_1.get(i);
                   if (bin_search(ar_2,st) == true)
                       System.out.println(st.id+ " "+st.name+" "+st.school);
               }

           }
           catch (IOException e) {
               e.printStackTrace();
           } finally {
               try {
                   if (br != null)br.close();
               } catch (IOException ex) {
                   ex.printStackTrace();
               }
           }
       }
       catch (IOException e) {
           e.printStackTrace();
       } finally {
           try {
               if (br != null)br.close();
           } catch (IOException ex) {
               ex.printStackTrace();
           }
       }
   }
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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