二进制搜索开始或结束是目标

Question

为什么当我看到二进制搜索的示例代码时，从来没有一个if语句来检查数组的开始还是结束是目标？

import java.util.Arrays;

public class App {

    public static int binary_search(int[] arr, int left, int right, int target) {
        if (left > right) {
            return -1;
        }

        int mid = (left + right) / 2;

        if (target == arr[mid]) {
            return mid;
        }

        if (target < arr[mid]) {
            return binary_search(arr, left, mid - 1, target);
        }

        return binary_search(arr, mid + 1, right, target);
    }

    public static void main(String[] args) {
        int[] arr = { 3, 2, 4, -1, 0, 1, 10, 20, 9, 7 };

        Arrays.sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println("Index: " + i + " value: " + arr[i]);
        }

        System.out.println(binary_search(arr, arr[0], arr.length - 1, -1));
    }
}

在本例中，如果目标是-1或20，搜索将进入递归。但是它添加了一个if语句来检查目标是否是mid，那么为什么不添加两个语句来检查它的左边还是右边呢？

Answer 1

你似乎有一种印象，“他们为中间添加了一个额外的支票，所以他们肯定也应该为开始和结束添加一个额外的支票”。

检查“是在目标中间吗？”事实上不仅仅是他们添加的优化。递归地检查“mid”是二进制搜索的全部要点。

当您有一个排序的元素数组时，二进制搜索是这样工作的：

null

对于一个拥有数十亿条目的大规模现实世界数据集？嗯，让我们考虑一下。为了简单起见，我们假定我们知道目标在数组中。

我们从整个阵列开始。第一个元素是目标吗？这种可能性是十亿分之一。不太可能。最后一个元素是目标吗？这种可能性也是十亿分之一。也不太可能。您浪费了两个额外的比较来加速一个极不可能的情况。

我们把自己限制在，比如说，前半部分。我们又做同样的事情。第一个元素是目标吗？可能不会，因为几率是5亿分之一。