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

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 语句来检查目标是否在中间，那么为什么不再添加两个语句来检查它是在左边还是在右边呢？

Answer 1

您的印象似乎是“他们为 mid 添加了一个额外的检查，所以他们肯定也应该为 start 和 end 添加一个额外的检查”。

检查“目标在中间吗？”实际上不仅仅是他们添加的优化。递归检查“mid”是二分查找的重点。

当你有一个排序的元素数组时，二分搜索的工作方式如下：

将中间元素与目标进行比较
1. 如果中间元素较小，则丢弃前半部分
2. 如果中间元素较大，则丢弃后半部分
3. 否则，我们找到了！
重复直到找到目标或没有更多元素。

检查中间的行为是确定继续搜索数组的哪一半的基础。

现在，假设我们还添加了开始和结束检查。这对我们有什么好处？好吧，如果在任何时候目标恰好位于片段的开头或结尾，我们将跳过几步并稍微早点结束。这是一个可能的事件吗？

对于包含一些元素的小玩具示例，是的，也许吧。

对于包含数十亿条目的庞大真实世界数据集？嗯，让我们考虑一下。为了简单起见，我们假设我们知道目标在数组中。

我们从整个数组开始。第一个元素是目标吗？发生这种情况的几率是十亿分之一。不太可能。最后一个元素是目标吗？发生这种情况的几率也是十亿分之一。也不太可能。你已经浪费了两次额外的比较来加速一个极不可能的情况。

我们只限于上半场。我们再次做同样的事情。第一个元素是目标吗？可能不是，因为几率是十亿分之一。

...等等。

数据集越大，start/end“优化”就越无用。事实上，在（最大优化）比较方面，算法的每一步都有三个比较，而不是通常的一个。非常粗略地估计，这表明算法平均变慢三倍。

即使对于较小的数据集，它的用途也很可疑，因为它基本上变成了准线性搜索而不是二分搜索。是的，几率更高，但平均而言，我们可以期待在达到目标之前进行更多的比较。

二分查找的全部意义在于通过尽可能少的无用比较来达到目标。添加更多不太可能成功的比较通常不是改善这种情况的方法。

编辑：

OP 发布的实现也可能会稍微混淆问题。该实现选择在 target 和 mid 之间进行 two 比较。更优化的实现将改为进行单一的三向比较（即确定“>”、“=”或“<”作为单个步骤而不是两个单独的步骤）。例如，这就是 Java 的 compareTo 或 C++ 的 <=> 通常的工作方式。

Answer 2

要为 start 和 end 添加一些额外的检查以及 mid 值是不怎么样。

在任何算法设计中，主要关注的是围绕它的复杂性移动它是时间复杂性 或 space 复杂度 。大多数时候，时间复杂度被视为更重要的方面。

要了解有关 Binary Search Algorithm 在不同用例中的更多信息，例如 -

如果数组不包含任何重复
如果Array在这种情况下有重复元素-

a) return最左边index/value

b) return 最右边 index/value

还有更多要点

Answer 3

BambooleanLogic 的回答是正确和全面的。我很好奇这个 'optimization' 使二进制搜索慢了多少，所以我写了一个简短的脚本来测试平均执行多少比较的变化：

Given an array of integers 0, ... , N 
do a binary search for every integer in the array,
and count the total number of array accesses made.

为了公平起见，我在针对目标检查 arr[left] 之后，将左侧增加 1，右侧也类似，这样每次比较都尽可能有用。你可以自己试试at Try it online

结果：

Binary search on size         10:   Standard         29  Optimized         43   Ratio  1.4828
Binary search on size        100:   Standard        580  Optimized       1180   Ratio  2.0345
Binary search on size       1000:   Standard       8987  Optimized      21247   Ratio  2.3642
Binary search on size      10000:   Standard     123631  Optimized     311205   Ratio  2.5172
Binary search on size     100000:   Standard    1568946  Optimized    4108630   Ratio  2.6187
Binary search on size    1000000:   Standard   18951445  Optimized   51068017   Ratio  2.6947
Binary search on size   10000000:   Standard  223222809  Optimized  610154319   Ratio  2.7334

所以总比较似乎确实倾向于标准数量的三倍，这意味着优化对更大的数组越来越无益。我很好奇限制比是否正好是3.

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

Binary search start or end is target

binary-search