c - 以最少的比较次数对大型数组中的多个不同数字进行二进制搜索

Question

我有一个大小为 n 的大数组(比如 n = 1000000)，其值单调非递减。我有一组“k”键值(比如 k = { 1,23,39,55,..})。假设键值已排序。我必须使用最少的比较次数在大数组中找到这些键值的索引。如何使用二进制搜索来搜索多个唯一值？为每个键值单独执行此操作需要进行大量比较。当我在同一个大数组上搜索另一个元素时，我能否以某种方式重用我在一次搜索中学到的一些知识？

Answer 1

1. 对针(您要搜索的值)进行排序。
2. 创建一个和针一样长的数组，每个元素都是一对索引。使用 {0, len(haystack)} 初始化每一对。这些对代表了我们对针的可能位置的所有了解。
3. 看看大海捞针中的中间值。现在对你的针中的那个值进行二进制搜索。对于所有较小的针，将上限(在第 2 步的数组中)设置为当前 haystack 索引。对于所有更大的针，设置下限。
4. 在您执行第 3 步时，请记录现在剩余的最大射程的指针。将其平分并将其用作新的中间值以重复步骤 3。如果最大范围是单数，则您已完成:已找到所有针(或者如果未找到，则它们在干草堆中的预期位置现在已知)。

当你在干草堆中有重复的值时，这里可能会有些复杂，但我认为一旦你解决了其余的问题，这应该不会太困难。

---

我很好奇 NumPy 是否实现了类似的东西。你正在做的事情的 Python 名称是 numpy.searchsorted()，一旦你通过了 API 层，它就会变成 this。 :

    /*
     * Updating only one of the indices based on the previous key
     * gives the search a big boost when keys are sorted, but slightly
     * slows down things for purely random ones.
     */
    if (@TYPE@_LT(last_key_val, key_val)) {
        max_idx = arr_len;
    }
    else {
        min_idx = 0;
        max_idx = (max_idx < arr_len) ? (max_idx + 1) : arr_len;
    }

所以他们没有像我描述的那样进行全面优化，但他们确实在当前针大于最后一根针时进行跟踪，他们可以避免搜索找到最后一根针的下方的大海捞针。这是对原始实现的简单而优雅的改进，从评论中可以看出，它必须保持简单和快速，因为该功能首先不需要对针进行排序。

---

顺便说一句:我提出的解决方案旨在实现类似于大 O 术语中的理论最优性，但如果您有大量针，最快的方法可能是对针进行排序，然后遍历整个大海捞针，然后串联所有针:线性搜索第一根针，然后从那里继续寻找第二根针，依此类推。您甚至可以通过识别针是否大于 A 且小于 C 来跳过大海捞针中的每第二个项目，它必须位于位置 B(假设您不关心不在干草堆中的针的左/右插入顺序)。然后，您可以进行 len(haystack)/2 比较，整个过程将对缓存非常友好(当然，在对针进行排序之后)。