二分搜索程序

Question

该代码是一个简单的二进制搜索程序。我试着追踪这个程序，但这只会让我更困惑。我不明白为什么嵌套的if语句包含data，min，midpoint - 1，& target，而底部的if语句包含data，midpoint + 1，max，target。

public static boolean binarySearch(int[] data, int min, int max, int target){
    boolean found = false;
    int midpoint = (min + max) / 2;  // determine the midpoint

    if (data[midpoint] == target)
        found = true;

    else if (data[midpoint] > target)
    {
        if (min <= midpoint - 1)
            found = binarySearch(data, min, midpoint - 1, target);
    }

    else if (midpoint + 1 <= max)
        found = binarySearch(data, midpoint + 1, max, target);

    return found;
}

Answer 1

二进制搜索递归地搜索左半部(min... mid-1)和右半部(mid+1...max)。

您正在对照target检查mid，这就是为什么它不在该范围内的原因。

你真的应该有一个if (min >= max) return false;的基本情况，以防止超出数组的界限。

下面是一个更清晰的实现，因为我发现它更容易理解

public static boolean binSearch(int[] data, int target) {
    return _binSearch(data, target, 0, data.length);
}

private static boolean _binSearch(int[] data, int target, int low, int high) {
    int mid = (low + high) / 2;

    if (low >= high) return false;

    if (data[mid] == target) return true;

    boolean foundLeft = _binSearch(data, target, low, mid);
    boolean foundRight = !foundLeft && _binSearch(data, target, mid+1, high);

    return foundLeft || foundRight;
}

Answer 2

数组数据已按从小到大的顺序排序

因此，它发现如果中点的值大于目标，则目标将出现在中点之前的值中。因此，我们只在中点的左侧递归调用该方法，即从min到中点之前的值的所有值。

类似地，如果中点小于目标，则可以在中点之后找到目标，因此我们只在中点的右侧递归调用该方法，即从中点之后的值到结束的所有值。

每次我们都不包括中点，因为它是在行中选中的

 if (data[midpoint] == target)

例如数组3 6 8 10 13 14 20。目标= 14中点将是=109索引4)。检查目标和中点，我们会看到目标大于中点，落在右边。因此，我们现在检查131420中的目标-从midpoint+1 (索引5)到结束。中点是14，上面的if语句将返回true。

Answer 3

使用范围(min, mid-1)将数据分成小于midpoint的一半，使用范围(mid+1, max)将数据划分为大于midpoint的一半。

如果您的输入为{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}和min = 0; max= 10，则

int midpoint = (0 + 10) / 2; // which is 5

如果data[midpoint]不是您要找的东西，那么需要查找所有的东西(但不是midpoint本身，这就是为什么里面有-1和+1的原因。)

因此，左半部分的范围是(0, 4)，右半部分的范围是(6, 10)。

如果你在找，比方说12，我们会往左走，因为data[midpoint] == 13 && 13 > 12

int midpoint = (0 + 4) / 2; // which is 2

从data[2] < 10开始，我们就向右转，使用min = 3; max = 4;等等。