0 
% java BinarySearch 1.txt < 2.txt

如果我有两个文本文件（1.txt 和 2.txt），其中 2.txt 包含不在 1.txt 中的值，那么二进制搜索如何为我们提供这些值？如果参数BinarySearch是一个键和一个排序数组，我看不出这是如何应用的。

下面是二分查找的代码：

import java.util.Arrays;

public class BinarySearch {

    // precondition: array a[] is sorted
    public static int rank(int key, int[] a) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if      (key < a[mid]) hi = mid - 1;
            else if (key > a[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] whitelist = In.readInts(args[0]);

        Arrays.sort(whitelist);

        // read key; print if not in whitelist
        while (!StdIn.isEmpty()) {
            int key = StdIn.readInt();
            if (rank(key, whitelist) == -1)
                StdOut.println(key);
        }
    }
}

根据维基百科，根据我的理解：二进制搜索或半间隔搜索算法在排序数组中找到指定值（输入“键”）的位置。

那么如何在两个文本文件中找到不常见的值呢？

4

3 回答 3

0 
while (!StdIn.isEmpty()) { //WHILE THE INPUT FILE (OR STANDARD INPUT) ISN'T EMPTY
            int key = StdIn.readInt();  //GET THE NEXT INTEGER
            if (rank(key, whitelist) == -1) // USE BINARY SEARCH TO SEARCH FOR THAT INTEGER
                StdOut.println(key); //PRINT WHEN IT'S NOT FOUND
        }

它正在执行 N 二进制搜索的代码，其中 N 是标准输入文件中的整数数。复杂度为 O(n * log n) + O(m * log n)。n 和 m 不同文件的大小。while 列表中的 n 和其他列表中的 m。如果 whilelist 比其他文件小得多，这将很有效。如果没有，最好对两个文件进行排序，然后使用合并排序的合并步骤来比较它们。

于 2012-07-10T05:53:26.587 回答
0

我认为创建哈希表将比修改的合并排序算法更好地比较仅包含整数的大文件。您所要做的就是读取第一个文件（它已经在做）并在读取时将整数放入某种哈希中桌子。一次读取一个 int 的下一个文件，main 中的循环正在执行该操作，计算 int 的哈希并比较该表是否包含与哈希对应的哈希表中的任何值。我假设了完美的哈希表，因此您可能需要在发生冲突时进行修改。

于 2012-07-10T07:46:29.937 回答
0

据我了解这个问题，您想知道该程序在（正确）确定 2.txt 中的条目不在 1.txt 中时是如何工作的。这有一个非常简单的答案。

该算法对数组白名单进行排序。它将 lo 指针初始化为指向元素 0，将 hi 指针初始化为指向元素 whitelist.length-1，它是白名单中的最后一个元素。数组段是第一次迭代的整个数组。必须对数组进行排序或排序才能使其正常工作。

对于每次连续迭代，如果在当前数组段的中间没有找到该值，则逻辑确定该值必须在中间以上的半段中还是中间以下的半段中。该半段，不包括旧的中间元素，成为下一次迭代的新搜索段。该算法调整 hi 和 lo 指针，以一次接近数组剩余段的一半，如果搜索值在数组中，则它必须在哪里。

最终，对于不在数组中的搜索值，hi 和 lo（因此 mid）将收敛到同一个元素，它将是搜索到的数组的最后一段，只有一个元素的段。如果该元素没有搜索值，则根据搜索值和该元素的值，hi 将变为 mid - 1 或 lo 将变为 mid + 1。无论哪种方式，while 继续条件都将变为 false，因为 lo < = hi 不再正确。新的剩余搜索段现在具有负大小。这可以解释为如果在 while 终止之前没有发生返回，那么搜索在任何先前的段中都没有找到值，并且没有剩余的段要搜索。因此，搜索值不能在数组中。

这个问题中给出的实现有效。我已经使用包含此处使用的 In 和 StdIn 类的 Princeton.edu 标准库对其进行了测试。我已经使用标准输入管道从命令行编译并运行它，以管道输入第二个文本文件。我不认为我会像这样实现这个应用程序，除非作为二进制搜索方法的演示，也许是为了一个类或检查一些技术。

这里有一些关于为什么使用二分搜索的进一步背景。使用二分查找的原因是为了获得平均 1.5*logBase2(n) 复杂度的最坏情况 2*logBase2(n) 执行复杂度。对不在数组中的值进行二进制搜索将始终是 2*logBase2(n) 比较的最坏情况。

二进制搜索远远优于仅从数组的一端开始并搜索每个元素直到找到匹配项或到达数组末尾的线性搜索。平均搜索可能约为 n/2，具体取决于数组中值的分布。对不在数组中的值的线性搜索总是会有 n 次比较的最坏情况。

在二分查找中，每对比较都会消除一半的可能性。最多可在 20 次比较中搜索 1024 个条目的数组。将其与线性搜索的最大值 1024 进行比较。对搜索数组的大小进行平方只会使二分搜索的比较次数加倍。二进制搜索可以搜索包含 1,048,576 个条目的数组，最多可进行 40 次比较。将其与线性搜索最大值 1,048,576 进行比较。

问题中给出的基本二进制搜索算法对于从排序或有序集合继承的对象非常有用，并且您必须实现自己的比较和搜索方法以重载继承的方法。只要您有一个比较来确定对象之间的较小、较大和相等，并且根据该比较对集合进行排序或排序，您就可以使用这种基本的二分搜索算法来搜索集合。

于 2012-07-30T09:34:15.370 回答