二进制搜索多次返回错误答案

Question

我已经实现了迭代二分搜索算法，其中 returns 找到的元素的索引（如果元素不在数组中则为 -1）：

public static int binarySearch(int[] array, int target) {
    int left = 0;
    int right = array.length - 1;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == target) {
            return mid;
        } else if (array[mid] < target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
}

当我尝试在一个不在数组中的元素上进行测试时，它 returns 正确答案，当我用数组进行测试时：{1,5,23,111} 并且目标是数字 5它返回了正确的结果，在这种情况下为 1，但是当我尝试使用相同的数组但返回 -1 的数字 111 时，我也尝试使用不同的数组和多个目标数字并且多次返回 -1 即使该数字存在于数组中，对为什么会发生这种情况有帮助吗？

Answer 1

您的程序中存在一些逻辑问题。

第一个问题是使用 else 和包含 return 语句的 if 条件。由于当 if 条件为 true 时该方法将 return，因此放置 else 是无用的。需要使用 else 来选择两个选项中的任何一个（即不是两个）。在将 return 语句与第一个选项一起使用后，您已经禁止了第二个选项。
第二个问题是 right 和 left 变量的计算错误。 逻辑应该是： 如果 target 大于 mid 处的数字，则忽略左半部分，为此，只需前进 left超出 mid 一位；否则（即如果 target 比 mid 处的数字 less），通过将 right 向后移动一个位置来忽略右半部分。

下面是工作程序：

public class BinarySearchDemo {

    public static void main(String[] args) {
        int arr[] = { 1, 5, 23, 111 };
        System.out.println(binarySearch(arr, 23));
        System.out.println(binarySearch(arr, 20));
    }

    public static int binarySearch(int[] array, int target) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = left + (right - 1) / 2;
            if (array[mid] == target) {
                return mid;
            }
            if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
}

输出：

2
-1

Answer 2

您的 left/right 进步倒退了。当当前mid位置的元素小于目标时，则需要搜索右半部分，当当前mid位置的元素大于目标时（else 块），你需要搜索左半部分。

您找到 5 正确的唯一原因是 mid 在第一次迭代中恰好是正确的。

切换 else if 和 else 块中的语句。

else if (array[mid] < target) { left = mid + 1; }
else { right = mid - 1; }

或者反转 else if 条件的比较意义。

else if (array[mid] > target) { right = mid - 1; }
else { left = mid + 1; }

Answer 3

问题出在您更新 left 和 right 时。您在错误的 if 语句中更新它们。

当array[mid] < target时，要更新left指针，在右子数组中查找，反之亦然

所以你的更新应该是这样的：

else if (array[mid] < target) { left = mid + 1; } 
else { right = mid - 1; }

Answer 4

想添加为评论，但还不能评论

用正确的逻辑修复代码后（如上面的答案），这里有一些地方需要改进你的代码：
不要这样做：int mid=(left+right)/2;
这样做：int mid = low + ((high - low) / 2); 或这个 int mid = (low + high) >>> 1;

参考这个post.

二进制搜索多次返回错误答案

Binary search returning wrong answer many times

java

binary-search