利用递归算法进行二元搜索

Question

帮助我。我是一个java新手，我卡在了二进制搜索递归中（stackoverflow错误），我在任何地方都找不到解决方案。

public class BinarySearch {
    public static int binAry (int ary[], int st, int lt, int val){
        if (st<=lt) {
            int mid = (st + (lt-st)) / 2;
            if (val > ary[mid]) {
                binAry(ary, mid+1, lt, val);
            }
            else if (val < ary[mid]) {
                binAry(ary, st, mid-1, val);
            }
            else{
                return mid;
            }
        }
        return -1;
    }
    public static void main (String[] args){
        BinarySearch bs = new BinarySearch();
        int [] numbers = {0,1,2,3,4,5};
        int x = 3;
        int pt = numbers.length;
        int p = bs.binAry(numbers, 0, pt-1, x);
        if (p == -1){
            System.out.println("Number not found.");
        }
        else{
            System.out.println("Number found at " + p);
        }
    }
}

Answer 1

在我看来，问题在于 (val > ary[mid]) 将永远评估为真。总是这样。因此，你的代码将进入一个无尽的循环，最终，导致StackOverFlow异常。

如果你跟踪你的代码中涉及的变量的值到这一点，你会注意到以下几点 价值 从未改变，自始至终都是其值3。还有： int mid = (st + (lt-st)) 2 同为 lt2 因为st + (lt - st) = st - st + lt (通过给它们分配任何你想要的值来进行测试)。所以即使你改变了st在 binAry(Berry, mid+1, lt, val)，真的没有任何影响。lt 永远 数字.长度 - 1 和 中间 将永远是52=2。

在下面添加以下代码 int mid = (st + (lt-st)) 2 自己检查。

System.out.println("st="+st);    
System.out.println("lt="+lt);
System.out.println("mid="+mid);

也许如果你解释一下你想做什么 我就能更好地理解这个问题 也许我就能帮助你找到一个解决方案

编辑：好的，再奉献了一点时间后，我发现了你的错误。把公式改一改。

int mid = (st + (lt-st)) / 2  // This is wrong
int mid = st + (lt-st) / 2;  // This is ok, notice the parentheses