递归二进制搜索(整数)

utugiqy6  于 2021-06-29  发布在  Java
关注(0)|答案(2)|浏览(355)

我已经写了这个基于递归的二进制搜索算法,但是我不能理解错误的原因。

// Only a sorted array must be entered for binary search to work
    public int binarySearch(int searchFor, int[] inArray, int from, int to){
        if (to >= from){
            int mid = (to-from)/2 + from;

            if (inArray[mid] == searchFor){
                return inArray[mid];
            } else if (inArray[mid] < searchFor){
                binarySearch(searchFor, inArray, ++mid, to);
            } else if (inArray[mid] > searchFor){
                binarySearch(searchFor, inArray, from, ++mid);
            }
        }
        return -1;
    }

线程“main”java.lang.StackOverflowerr中出现异常

at search.binarySearch(search.java:24)
at search.binarySearch(search.java:24)
at search.binarySearch(search.java:24)
at search.binarySearch(search.java:24)
fslejnso

fslejnso1#

一些问题和评论:
在最后一种情况下,值 ++mid 是错误的 binarySearch . 该值应小于1 mid 那样的话。
我也会投票反对使用 ++mid 或者 --mid 这表明 mid 更改不需要的值。你应该过去 mid+1 在第一种情况下 mid-1 在第二个。 binarySearch 返回一个 int ,但是当您的代码递归调用它时,它不会对该返回值执行任何操作。
您应该返回该值。所以:

} else if (inArray[mid] < searchFor){
                return binarySearch(searchFor, inArray, mid+1, to);
//              ^^^^^^                                  ^^^^^
            } else if (inArray[mid] > searchFor){
                return binarySearch(searchFor, inArray, from, mid-1);
//              ^^^^^^                                        ^^^^^
            }

表达式 (to-from)/2 + from 是一种冗长的做法 (from+to)/2 ...

xam8gpfp

xam8gpfp2#

除了添加 return 到的递归调用 binarySearch ,逻辑上有几个缺陷: mid 应递减以捕捉左侧部分中的值:

return binarySearch(searchFor, inArray, from, --mid);

应该有一张有效的支票 mid , from , to 输入数组中的值
因此,该方法应如下所示:

public static int binarySearch(int searchFor, int[] inArray, int from, int to) {
        if (to >= from && from > -1 && to <= inArray.length) {
            int mid = (to-from)/2 + from;

            if (mid >= inArray.length) {
                return -1;
            }

            // System.out.printf("from=%d to=%d mid=%d val=%d%n", from, to, mid, inArray[mid]); // debug print
            if (inArray[mid] == searchFor) {
                return inArray[mid];
            } else if (inArray[mid] < searchFor){
                return binarySearch(searchFor, inArray, ++mid, to);
            } else {
                return binarySearch(searchFor, inArray, from, --mid);
            }
        }
        return -1;
    }
}

测验:

public static int binarySearch(int searchFor, int... inArray) {
    System.out.printf("Searching for %d in %s%n", searchFor, Arrays.toString(inArray));
    return binarySearch(searchFor, inArray, 0, inArray.length);
}

System.out.println(binarySearch(10));
    System.out.println(binarySearch(10, 10));
    System.out.println(binarySearch(10, 1));
    System.out.println(binarySearch(10, 0, 1, 5, 8, 10, 21));
    System.out.println(binarySearch( 0, 0, 1, 5, 8, 10, 21));
    System.out.println(binarySearch(21, 0, 1, 5, 8, 10, 21));

    System.out.println(binarySearch(10, 0, 1, 3, 5, 8, 10, 21));
    System.out.println(binarySearch( 0, 0, 1, 5, 8, 10, 15, 21));
    System.out.println(binarySearch(21, 0, 1, 5, 8, 10, 16, 21));

    System.out.println(binarySearch(30, 0, 1, 5, 8, 10, 21));
    System.out.println(binarySearch(-1, 0, 1, 5, 8, 10, 21));
    System.out.println(binarySearch(7, 0, 1, 5, 8, 10, 21));

输出:

Searching for 10 in []
-1
Searching for 10 in [10]
10
Searching for 10 in [1]
-1
Searching for 10 in [0, 1, 5, 8, 10, 21]
10
Searching for 0 in [0, 1, 5, 8, 10, 21]
0
Searching for 21 in [0, 1, 5, 8, 10, 21]
21
Searching for 10 in [0, 1, 3, 5, 8, 10, 21]
10
Searching for 0 in [0, 1, 5, 8, 10, 15, 21]
0
Searching for 21 in [0, 1, 5, 8, 10, 16, 21]
21
Searching for 30 in [0, 1, 5, 8, 10, 21]
-1
Searching for -1 in [0, 1, 5, 8, 10, 21]
-1
Searching for 7 in [0, 1, 5, 8, 10, 21]
-1

相关问题