(UVA) CD - Solution 1

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2949

Due to the fact that Jack and Jill will only sell the CDs that they have in common, the solution below is using a Binary Search to find out all the CDs that Jill has in common with Jack.


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

class Main {
    public static int[] cdsJack;
    public static int[] cdsJill;
   
    public static boolean binarySearch(int lo, int hi, int cdID) {
        if (lo > hi) {
            return false;
        }
       
        int mi = (lo+hi)/2;
        if (cdsJill[mi] > cdID) {
            return binarySearch(lo, mi-1, cdID);
        }
        else if (cdsJill[mi] < cdID) {
            return binarySearch(mi+1, hi, cdID);
        }
        else {
            return true;
        }
    }
   
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numCDsJack = sc.nextInt();
        int numCDsJill = sc.nextInt();
        while (numCDsJack != 0 || numCDsJill != 0) {
            cdsJack = new int[numCDsJack];
            for (int i = 0; i < numCDsJack; i++) {
                cdsJack[i] = sc.nextInt();
            }
            cdsJill = new int[numCDsJill];
            for (int i = 0; i < numCDsJill; i++) {
                cdsJill[i] = sc.nextInt();
            }
           
            int countCommon = 0;
            for (int i = 0; i < numCDsJack; i++) {
                boolean gotCommon = binarySearch(0, numCDsJill-1, cdsJack[i]);
                if (gotCommon) {
                    countCommon++;
                }
            }
           
            System.out.println(countCommon);
           
            numCDsJack = sc.nextInt();
            numCDsJill = sc.nextInt();
        }
                                       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}