二分查找多次返回错误答案

Question

我已经实现了迭代二分搜索算法，该算法返回找到的元素的索引（如果该元素不在数组中，则返回-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;

}

当我尝试在不在数组中的元素上测试它时，它返回正确的答案，当我用数组尝试它时：{1,5,23,111}并且目标是数字 5，它返回正确的结果，在本例中为 1，但是当我尝试使用相同的数组，但它返回的数字 111 -1，我也尝试过使用不同的数组和多个目标数字，很多次它返回 -1，即使该数字存在于数组中，任何帮助说明为什么会这样发生？

Answer 1

您的左/右前进是向后的。当当前位置的元素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 2

您的程序存在一些逻辑问题。第一个问题是使用else包含语句if的条件return。由于该方法会return在if条件为时执行true，因此添加 anelse是没有用的。需要使用 来else选择两个选项中的一个（即不是两者都选择）。使用return带有第一个选项的语句后，您已经禁止第二个选项。right第二个问题是和变量的计算放错了位置left。逻辑应该是：target如果大于 处的数字，则忽略左半部分mid，为此，只需left在 之外前进一位即可mid；否则（即，如果target大于less处的数字），通过向后mid移动一个位置来忽略右半部分。right工作方案如下：public class BinarySearchDemo {&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; &nbsp; &nbsp; int arr[] = { 1, 5, 23, 111 };&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(binarySearch(arr, 23));&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(binarySearch(arr, 20));&nbsp; &nbsp; }&nbsp; &nbsp; public static int binarySearch(int[] array, int target) {&nbsp; &nbsp; &nbsp; &nbsp; int left = 0;&nbsp; &nbsp; &nbsp; &nbsp; int right = array.length - 1;&nbsp; &nbsp; &nbsp; &nbsp; while (left <= right) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int mid = left + (right - 1) / 2;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (array[mid] == target) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return mid;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (array[mid] < target) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; left = mid + 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; right = mid - 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return -1;&nbsp; &nbsp; }}输出：2-1

Answer 3

问题是当你更新left和right. 您正在错误的 if 语句中更新它们。当 时array[mid] < target，您想要更新left指针并在右侧子数组中搜索，反之亦然。所以你的更新应该是这样的：else if (array[mid] < target) { left = mid + 1; }&nbsp;else { right = mid - 1; }

Answer 4

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