java.lang.StackOverflowError in Binary Search Algorithm

Question

你们能帮帮我吗？我收到错误：

Exception in thread "main" java.lang.StackOverflowError
    at binarysearch.search(binarysearch.java:22)
    at binarysearch.search(binarysearch.java:31)

（二进制搜索.java：31重复十几次）。我一直在试图理解递归，但我想我在某个地方失败了。

public class binarysearch {
    static int[] arr = new int[100];
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        fill();
        if (search(31, arr, 1, 30)) {
            System.out.println("true");
        } else {
            System.out.println("false");
        }
    }
    public static void fill() {
        for(int i = 1; i < 30; i++) {
            arr[i] = i;
        }
    }
    public static boolean search(int value, int[] data, int start, int end) {
        int len = end - start + 1 ;
        int mid = (start + end) / 2;
        if (len == 1) {
            return false;
        } else {
            if (data[mid] == value) {
                return true;
            } else {
                if (data[mid] < value) {
                    return search(value, data, mid, end);
                } else {
                    return search(value, data, start, mid);
                }
            }
        }
    }
}

Answer 1

来自 search(31, arr, 1, 30) 你会遇到

1， 30

票价：15、30

票价：22、30

票价：26、30 元

28、30

票价：29、30 元

票价：29、30 元

票价：29、30 元

....

并成为无限栈溢出

所以你的算法应该是

public static boolean search(int value, int[] data, int start, int end) {
    int len = end - start + 1 ;
    int mid = (start + end) / 2;
    if (len == 1) {
        return false;
    } else {
        if (data[mid] == value) {
            return true;
        } else {
            if (data[mid] < value) {
                return search(value, data, mid + 1, end);
            } else {
                return search(value, data, start, mid - 1);
            }
        }
    }
}

Answer 2

尝试将递归调用更改为：

if (data[mid] < value) {
    return search(value, data, mid+1, end);
} else {
    return search(value, data, start, mid-1);
}