自定义二进制搜索功能无法正常工作

Question

我正在创建自定义的二叉搜索函数，但遇到了问题。我已经浏览了代码很长时间了，但是，我无法弄清楚为什么没有任何返回。请让我知道你的想法。谢谢！

a 是数组，b 是最后返回的结果，t 是目标值。Pos 是当前位置，最小值和最大值是最小和最大位置。

public static int binarySearch(int a[], int t){
    int min = 0;
    int max = a.length;
    if (a[0] == t){
        return 0;
    }
    int b = -1;
    for (int pos = min; a[pos] != t;){
        pos = (max - min) / 2;
        if (a[pos] == t){
            b = pos;
        } else {
            if(t > a[pos]){
                min = pos + 1;
            } else {
                min = pos - 1;
            }
        }
    }
    return b;
}

Answer 1

两个小问题

pos = (max - min) / 2;

看起来您正在尝试找到值的平均值，但实际上却找到了一半的差异

相反，要找到平均值，请使用pos = (max - min) / 2 + min;

此外，当将max向下移动时，您不小心将min向上移动

min = pos - 1;应该改为max = pos - 1;

Answer 2

我看到您的代码存在三个问题：

1. 您的循环条件不足以确定整个过程的终止。您的循环条件是a[pos] != t的，并且您只会增加或减少pos，如果我们搜索的元素在数组中找不到，最终会导致ArrayIndexOutOfBoundsException。

2. 您的 if-else 不正确，因为您只更新最小值而不是最大值的值。

3. 与其每次都"移动"pos的值一半，不如将其设置为最小值和最大值的平均值，这是不正确的。

结合以上所有内容，您将获得以下结果：

public static int binarySearch(int a[], int t) {
    int min = 0;
    int max = a.length;
    if (a[0] == t) {
        return 0;
    }
    int b = -1;
    for (int pos = min; a[pos] != t;) {
        pos = min + (max - min) / 2;
        if (pos >= a.length || pos <= 0) {
            break;
        }
        if (a[pos] == t) {
            b = pos;
        } else {
            if (t > a[pos]) {
                min = pos + 1;
            } else {
                max = pos - 1;
            }
        }
    }
    return b;
}