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

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

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

1. 第一个问题是使用else包含语句if的条件return。由于该方法会return在if条件为时执行true，因此添加 anelse是没有用的。需要使用 来else选择两个选项中的一个（即不是两者都选择）。使用return带有第一个选项的语句后，您已经禁止第二个选项。

2. right第二个问题是和变量的计算放错了位置left。逻辑应该是：target如果大于 处的数字，则忽略左半部分mid，为此，只需left在 之外前进一位即可mid；否则（即，如果target大于less处的数字），通过向后mid移动一个位置来忽略右半部分。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 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;