题解 | #数值的整数次方#

//看了这么多题解，很少用二分的
//我这个二分每次是半边二分，但比双指针一格移动要快些

 public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
        //二分：主要思想是怎么把区间缩短一半
        /*
           思路：
            1）本题可以根据l + mid 来二分，也可以根据r + mid来二分
            做二分题时，只使用其中一个条件来分割区间就行，否则情况太多了，脑子容易乱

            2）也可以使用对撞双指针，不过每次只移动一格
        */
         ArrayList<Integer> res = new ArrayList<Integer>();
        if(array.length <= 0)
            return res;

        int l = 0;
        int r = array.length - 1;
        while(l + 1 < r){
            int mid = l + (r - l) / 2;
            if(array[l] + array[r] == sum){
                res.add(array[l]);
                res.add(array[r]);
                return res;
            }
            if(array[mid] + array[r] < sum){
                l = mid;
            }else if(array[mid] + array[r] > sum){
                r--;
            }else{
                res.add(array[mid]);
                res.add(array[r]);
                return res;
            }
        }
        //判断剩余
        if(array[l] + array[r] == sum){
                res.add(array[l]);
                res.add(array[r]);
                return res;
        }else
            return res;

    }