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

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，因此放置else是无用的。需要使用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语句更新它们。

Answer 4

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