二分查找算法中的java.lang.StackOverflowError

Question

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

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

(binarysearch.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

...

并成为无限的stackOverFlow

所以你的算法应该是

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);
            }
        }
    }
}