二分搜索程序

Question

代码是一个简单的二分搜索程序。我试着追踪程序，但它只会让我更加困惑。我不明白为什么嵌套的if has data,min,midpoint-1,&target和底部的else if语句has 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

数组数据已从最小到最大排序

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

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

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

 if (data[midpoint] == target)

例如阵列3、6、8、10、13、14、20。target=14中点将是=10 9index 4）。检查target和midpoint，我们会看到target大于中点，并且落在右边。所以我们现在在13 14 20中检查target--从midpoint+1（index 5）直到结尾。中点将是14。并且上面的if语句将返回true。