二分查找处理不当引起的堆栈溢出异常

        在刷题的时候，使用了二分查找找出目标数在升序数组的位置，但是一运行发现报错提示堆栈异常，即不断地递归，而没有走到递归出口逻辑。

一、算法题：和为S的两个数字

        输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。

数据范围: 0 < len(array) <10^5 ​​， 1 < array[i]  < 10^6 

         我想到的解题思路是先通过二分查找，找出目标数在数组中最应该出现的位置，然后再找出子数组中满足条件的两个数。所以使用到了二分查找。代码如下：

import java.util.*;
import java.util.ArrayList;
public class Solution {
    public ArrayList FindNumbersWithSum(int [] array,int sum) {
        //先用二分查找找出sum在升序数组中，保证插入后依然有序的情况下，应该插入的位置
        //然后从左边的子数组中寻找符合条件的两个数
        ArrayList targetList = new ArrayList<>();
        int targetIndex = binarySearch(array, sum + 0.5, 0, array.length - 1);
        int head = 0; //头指针
        int tail = targetIndex; //尾指针
        while (head < tail) {
            if (array[head] + array[tail] == sum) {
                targetList.add(array[head]);
                targetList.add(array[tail]);
                break;
            } else if (array[head] + array[tail] > sum) {
                tail--;
            } else {
                head++;
            }
        }
        return targetList;
    }
    
    //二分查找找出最靠近double类型sum值的下标为止
    public int binarySearch(int [] array, double sum, int start, int end) {
        if (start >= end) return start;
        int mid = (start + end) / 2;
        if (array[mid] > sum) {
            end = mid;
        } else {
            start = mid;
        }
        return binarySearch(array, sum, start, end);
    }
}

一运行就报错如下：

请检查是否存在数组越界等非法访问情况
Exception in thread "main" java.lang.StackOverflowError
at Solution.binarySearch(Solution.java:34)
at Solution.binarySearch(Solution.java:34)
at Solution.binarySearch(Solution.java:34)
at Solution.binarySearch(Solution.java:34)
at Solution.binarySearch(Solution.java:34)
at Solution.binarySearch(Solution.java:34)
at Solution.binarySearch(Solution.java:34)

输入的测试数据为：array=[1,4,9], sum=8

二、异常原因分析

//二分查找找出最靠近double类型sum值的下标为止
public int binarySearch(int [] array, double sum, int start, int end) {
    if (start >= end) return start;
    int mid = (start + end) / 2;
    if (array[mid] > sum) {
        end = mid;
    } else {
        start = mid;
    }
    return binarySearch(array, sum, start, end);
}

        问题出在二分查找实现上，对start和end动态调整是错误的。

        就拿array=[1,4,9]数组来分析

1、参数：sum=8.5, start=0, end=2；

2、进入函数内部逻辑， 不满足start >= end，所以接着求mid=(0 + 2)/ 2 = 1。array[1]=4<8.5,所以end=mid=1; 接着使用新参数调用了函数本身；

3、参数：sum=8.5, start=1, end=2；

4、进入函数内部逻辑， 不满足start >= end，所以接着求mid=(1 + 2)/ 2 = 1。array[1]=4<8.5,所以end=mid=1; 接着使用新参数调用了函数本身；

5、参数：sum=8.5, start=1, end=2；

6、这时就发现，程序进入死循环了！！！

        如你所看到的，计算出的start=1, end=2，其mid=1，如果函数中不对mid进行+1或-1，则mid永远不变。start永远不会有大于等于end的情况。

        要想能走到递归函数的出口，则在处理mid的时候就必须对mid进行左移-1或右移+1。

        所以，在对start和end动态调整的时候，不能把mid直接赋值给它们，而是必须下面这样：

//二分查找找出最靠近double类型sum值的下标为止
public int binarySearch(int [] array, double sum, int start, int end) {
    if (start >= end) return start;
    int mid = (start + end) / 2;
    if (array[mid] > sum) {
        end = mid - 1;
    } else {
        start = mid + 1;
    }
    return binarySearch(array, sum, start, end);
}

接着运行程序，通过了！