题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

import java.util.ArrayList;

public class Solution {
    
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        
        ArrayList<Integer> a = new ArrayList<Integer>();
        int first = 0;
        int second = 0;
        int min = Integer.MAX_VALUE;
        for(int i = 0; i < array.length; i++) {
            
            if(array[i] > sum)
                break;
            if(array[i] > sum - array[i])
                break;
            int temp  = sum - array[i];
            if(binarySearch(array, temp)) {
                
                if(array[i] * temp < min){
                    
                    first = array[i];
                    second = temp;
                    min = first * second;
                }
            }
        }
        if(first == 0 || second == 0) 
            return a;
        a.add(first);
        a.add(second);
        return a;
    }
    private boolean binarySearch(int[] a, int key) {
        
        if(a == null || a.length == 0)
            return false;
        return search(a, 0, a.length - 1, key);
    }
    private boolean search(int[] a, int left, int right, int key) {
        
        if(left > right)
            return false;
        int mid = (left + right) / 2;
        if(a[mid] == key)
            return true;
        if(a[mid] < key)
            return search(a, mid + 1, right, key);
        else
            return search(a, left, mid - 1, key);
    }
}