(UVA) Closest Sums - Solution 2

If you want to see another solution for this problem, click here.

The difference between this solution and the previous one is that here a Binary Search is used to find the closest sum.


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

class Main {
    public static ArrayList<Integer> sums;
   
    public static int binarySearch(int lo, int hi, int value) {
        if (lo > hi) {
            return lo;
        }

        int mi = (lo+hi)/2;
        if (sums.get(mi) < value) {
            return binarySearch(mi+1, hi, value);
        }
        else if (sums.get(mi) > value) {
            return binarySearch(lo, mi-1, value);
        }
        else {
            return mi;
        }
    }
   
    public static int reader(BufferedReader br) throws NumberFormatException, IOException {     
        int n;
        int resp = 0;     
        int signal = 1;
       
        while (true) {         
            n = br.read();         
            if (n >= '0' && n <= '9') {
                break;
            }
            if (n == '-') {
                signal = -1;
            }
            if (n == '+') {
                signal = 1;
            }
        }
           
        while (true) {         
            resp = resp*10 + n-'0';         
            n = br.read();         
            if (n < '0' || n > '9') {
                break;     
            }
        }
      
        return resp*signal;     
    }
   
    public static void process() throws NumberFormatException, IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       
        int numCase = 0;
        int qtyNum = reader(br);
        while (qtyNum > 0) {
            int[] setInt = new int[qtyNum];
            for (int i = 0; i < qtyNum; i++) {
                setInt[i] = reader(br);
            }
           
            int qtyQueries = reader(br);
            int[] queries = new int[qtyQueries];
            for (int i = 0; i < qtyQueries; i++) {
                queries[i] = reader(br);
            }
           
            sums = new ArrayList<Integer>();
            for (int i = 0; i < qtyNum; i++) {
                for (int j = i+1; j < qtyNum; j++) {
                    int sum = setInt[i]+setInt[j];
                    sums.add(sum);
                }
            }
           
            Collections.sort(sums);
           
            System.out.println("Case " + ++numCase + ":");
            for (int i = 0; i < qtyQueries; i++) {
                int index = binarySearch(0, sums.size()-1, queries[i]);
                if (index >= sums.size()) {
                    index--;
                }
                if (sums.get(index) != queries[i]) {
                    if (index-1 >= 0) {
                        int diffLeft = Math.abs(queries[i]-sums.get(index-1));
                        int diffRight = Math.abs(queries[i]-sums.get(index));
                        if (diffLeft < diffRight) {
                            index = index-1;
                        }
                    }
                }
               
                System.out.println("Closest sum to " + queries[i] + " is " + sums.get(index) + ".");
            }
           
            qtyNum = reader(br);
        }
                   
        return;
    }
  
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();

        System.exit(0);
    }
}