带间隙的二分查找

Question

让我们想象一下这样的两个数组： [8,2,3,4,9,5,7]

[0,1,1,0,0,1,1]

我怎样才能只对下面有 1 的数字执行二进制搜索，而忽略其余部分？我知道这可以在 O(log n) 比较中进行，但是我当前的方法比较慢，因为它必须经过所有 0 直到达到 1。

Answer 1

如果您命中了下方为 0 的数字，则需要双向扫描下方为 1 的数字，直到找到它 -- 否则本地搜索 space 已用完。由于对 1 的扫描是线性的，因此 0 与 1 的比率决定了生成的算法是否仍然比线性更快。

Answer 2

这个问题很老了，但我刚刚发现了一个绝妙的小技巧，可以在大多数情况下解决这个问题。我正在写这个答案，以便我可以在其他地方参考它：

排序数组中的快速追加、删除和二进制搜索

需要在排序集合中动态插入或删除项目，同时保留搜索能力，通常迫使我们从使用二分搜索的简单数组表示切换到某种搜索树——一种复杂得多的搜索树数据结构。

但是，如果您只需要在末尾插入（即，您总是插入最大或最小的项目），或者根本不需要插入，则可以使用更简单的数据结构.它包括：

项目的动态（可调整大小）数组，项目数组；和
动态整数数组，集合数组。集合数组用作disjoint set data structure, using the single-array representation described here:

两个数组的大小始终相同。只要没有删除，item 数组就只包含按排序顺序排列的项目，而 set 数组充满了与这些项目对应的单例集。

但是，如果项已被删除，则项数组中的项仅在集合数组中相应位置存在根集时才有效。已合并为单个根的所有集合在集合数组中将是连续的。

该数据结构支持如下所需的操作：

追加 (O(1))

要追加一个新的最大项目，只需将项目追加到项目数组，然后将一个新的单例集追加到集合数组。

删除（有效摊销 O(log N)）

要删除有效项目，请先调用搜索以查找相邻的较大有效项目。如果没有更大的有效项目，则只需截断两个数组以删除该项目和所有相邻的已删除项目。由于合并集在集合数组中是连续的，这将使两个数组处于一致状态。

否则，合并集合数组中已删除项和相邻项的集合。如果已删除项的集合被选为新的根，则将相邻项移动到项数组中已删除项的位置。没选的那个位置以后就不用了，必要的时候可以清空释放引用。

如果删除后只有不到一半的项目数组有效，则应从项目数组中删除已删除的项目，并将集合数组重置为全单例状态。

搜索（有效摊销 O(log N)）

二分查找正常进行，除了我们需要为每个测试位置找到代表项：

int find(item_array, set_array, itemToFind) {
    int pos = 0;
    int limit = item_array.length;
    while (pos < limit) {
        int testPos = pos + floor((limit-pos)/2);
        if (item_array[find_set(set_array, testPos)] < itemToFind) {
            pos = testPos + 1; //testPos is too low
        } else {
            limit = testPos; //testPos is not too low
        }
    }
    if (pos >= item_array.length) {
        return -1;  //not found
    }
    pos = find_set(set_array, pos);
    return (item_array[pos] == itemToFind) ? pos : -1;
}

带间隙的二分查找

Binary search with gaps

language-agnostic

algorithm

data-structures

排序数组中的快速追加、删除和二进制搜索

追加 (O(1))

删除（有效摊销 O(log N)）

搜索（有效摊销 O(log N)）