使用二分查找找到多个条目

Question

我使用标准的二分查找来快速返回已排序列表中符合可排序属性的单个对象。

现在我需要修改搜索算法，以便返回所有匹配的列表项。应该如何最好地做到这一点？

- Gruber

---

什么语言？“标准”的二分查找可能会有所不同或具有一些方便的重载。 - Colin D

@ColinD：我目前在Java中使用自己的实现。只有大约十几行代码。 - Gruber

Answer 1

好的，由于列表已经排序，你感兴趣的所有条目都是连续的。这意味着你需要从二分搜索产生的索引开始向后查找第一个等于找到项的条目。最后一个条目也是同样的方法。

你可以简单地从找到的索引开始向后查找，但是如果有很多与找到项相等的项，这种解决方案可能会变得像O(n)一样慢。因此，你最好使用指数搜索：在找到更多匹配项时，使跳跃翻倍。这样，整个搜索仍然是O(log n)。

- Vlad

---

为什么只倒退而不前进呢？ - Muhammad Umer

@Muhammad：当然，你是正确的：同样适用于寻找上界。 - Vlad

@Vlad第二个部分可能有误或缺失。当你的边界在第(n-2)个元素时，你会怎么做？你最后一次跳跃(n/2)将失败（假设n是2的幂）。那么现在你该怎么办？如果你扫描它，则时间复杂度为O(n)。如果你采用相同的技术，在(n/4)次跳跃处再次失败。等等……你能证明它的时间复杂度为O(log n)吗？ - Elad Weiss

Answer 2

首先让我们回想一下简单的二分查找代码片段：

int bin_search(int arr[], int key, int low, int high)
{
    if (low > high)
        return -1;

    int mid = low + ((high - low) >> 1);

    if (arr[mid] == key) return mid;
    if (arr[mid] > key)
        return bin_search(arr, key, low, mid - 1);
    else
        return bin_search(arr, key, mid + 1, high);
}

引用自Skiena教授： 如果我们从上面的实现中删除相等测试 if(s[middle] == key) 返回(middle); 并在每次不成功的搜索中返回索引low而不是-1。由于没有相等测试，所有搜索现在都将失败。 当关键字与相同的数组元素进行比较时，搜索将继续到右半部分，最终在右边界处终止。 在二进制比较方向反转后重复搜索将导致我们达到左边界。每次搜索都需要O(lgn)时间， 因此，无论块的大小如何，我们可以在对数时间内计算出发生的次数。

因此，我们需要两轮二分搜索来找到lower_bound（查找第一个不小于KEY的数）和upper_bound（查找第一个大于KEY的数）。

int lower_bound(int arr[], int key, int low, int high)
{
    if (low > high)
        //return -1;
        return low;

    int mid = low + ((high - low) >> 1);
    //if (arr[mid] == key) return mid;

    //Attention here, we go left for lower_bound when meeting equal values
    if (arr[mid] >= key) 
        return lower_bound(arr, key, low, mid - 1);
    else
        return lower_bound(arr, key, mid + 1, high);
}

int upper_bound(int arr[], int key, int low, int high)
{
    if (low > high)
        //return -1;
        return low;

    int mid = low + ((high - low) >> 1);
    //if (arr[mid] == key) return mid;

    //Attention here, we go right for upper_bound when meeting equal values
    if (arr[mid] > key) 
        return upper_bound(arr, key, low, mid - 1);
    else
        return upper_bound(arr, key, mid + 1, high);
}

希望它有所帮助 :)

- user2696499

---

当使用大小为10,000的数组运行此代码时，会出现StackOverflowError。 - Big Al

我认为每个“high - 1”应该改为“mid - 1”，每个“low + 1”应该改为“mid + 1”。 - Big Al

非常好用！但是我尝试在一个不包含你要查找的元素的数组中使用它（例如：在数组[1,1,3,4,5]中搜索键2）。它会返回下限2和上限5。因此，在if (low > high)之后，我添加了一个额外的检查，如果low处的元素在数组范围内（>0 <size）并且与键匹配，则执行该操作。 - Alexei

(上界和下界)算法的时间复杂度是什么？ - aman_49

Answer 3

如果我理解正确，您有一个对象列表，为了比较，看起来像 {1,2,2,3,4,5,5,5,6,7,8,8,9}。普通的搜索会命中与 5 相比较的某个对象，但是您想要获取它们所有的值，对吗？

在这种情况下，我建议使用标准的二分查找算法，当其找到匹配元素时，从左侧开始查找直到不再匹配，然后再从第一个匹配项开始向右侧查找直到不再匹配。

请注意，您正在使用的任何数据结构都不会覆盖与之相同的元素！

或者，考虑使用一种结构，在该位置存储与之相同的元素作为一个桶。

- Miquel

---

谢谢，这就是我认为会有成果的东西。但是代码变得相当丑陋。我希望有人能提供一个简短的递归解决方案之类的东西…… :) - Gruber

不需要丑陋。你应该有一个函数来执行二分查找并返回值的索引，然后进行线性搜索，通过传入一个初始索引返回其余的值，可能需要递归调用自身来搜索左边和右边。 - nlucaroni

Answer 4

一旦您使用bsearch找到匹配项，只需递归地在两侧进行bsearch，直到没有更多匹配项。

伪代码:

    range search (type *array) {
      int index = bsearch(array, 0, array.length-1);

      // left
      int upperBound = index -1;
      int i = upperBound;
      do {
         upperBound = i;
         i = bsearch(array, 0, upperBound);
      } while (i != -1)

      // right
      int lowerBound = index + 1;
      int i = lowerBound;
      do {
         lowerBound = i;
         i = bsearch(array, lowerBound, array.length);
      } while (i != -1)

      return range(lowerBound, UpperBound);
}

没有涵盖任何特殊情况。我认为这将使您的复杂度保持在（O(logN)）。

- yngccc

Answer 5

我会做两个二分查找，一个查找第一个与值比较的元素（在C++中是lower_bound），另一个查找第一个与值比较的元素（在C++中是upper_bound）。从lower_bound到upper_bound之前的元素就是你要找的（在java.util.SortedSet中表示为subset(key, key)）。

因此，您需要对标准二分搜索进行两个不同的轻微修改：仍然探测并使用探测中的比较来缩小您要查找的值必须位于其中的区域，但现在例如对于lower_bound，如果相等，则所有您知道的是找到的元素（第一个相等的值）在到目前为止的范围内的第一个元素和您刚刚探测的值之间 - 您不能立即返回。

- mcdowella

---

这是正确的做法，函数 lower bound/higher bound 是许多库中实现为此类函数的。 - user1228608

Answer 6

这段Java代码可以在一次遍历中以O(logN)时间计算已排序数组中目标值的出现次数。很容易将其修改为返回找到的索引列表，只需传入ArrayList。

思路是递归地缩小e和b边界，直到它们成为具有目标值的连续块的下限和上限；

static int countMatching(int[] arr, int b, int e, int target){
    int m = (b+e)/2;
    
    if(e-b<2){
        int count = 0;
        if(arr[b] == target){
            count++;
        }
        if(arr[e] == target && b!=e){
            count++;
        }
        return count;
    }
    else if(arr[m] > target){
        return countMatching(arr,b,m-1, target);
    }
    else if(arr[m] < target){
        return countMatching(arr, m+1, e, target);
    }
    else {
        return countMatching(arr, b, m-1, target) + 1 
            + countMatching(arr, m+1, e, target);
    }
}

- Dominik G

Answer 7

这取决于您使用的二分查找实现方式：

• 在Java和.NET中，二分查找将给出任意元素；您必须双向搜索以获取所需范围。
• 在C++中，您可以使用 equal_range 方法一次性生成所需结果。

为了加快Java和.NET中搜索的速度，当等值范围太长以至于无法线性迭代时，您可以寻找前驱元素和后继元素，并取范围中间的值，不包括两端。

如果由于进行第二个二分查找而导致速度过慢，请考虑编写自己的搜索，同时查找两端。这可能有点繁琐，但应该运行得更快。

- Sergey Kalinichenko

---

谢谢，我正在使用自己的实现。通常，任何语言提供的实现只返回一个元素。 - Gruber

@Gruber 在C++中不是这样的，它会返回整个范围。你可能想看一下它们的实现并了解它们是如何做到的，这很聪明，而且将equal_range翻译成你选择的语言也不应该太难。 - Sergey Kalinichenko

Answer 8

首先，根据可排序属性（使用“正常”二分查找），找到单个元素的索引，然后开始查找该元素在列表中左右两侧的所有元素，将所有符合搜索条件的元素添加到结果中，在某一端时停止搜索，当一个元素不符合条件或没有更多元素可遍历时停止搜索，并在左右两端同时满足上述停止条件时完全停止搜索。

- Óscar López

---

谢谢。看起来这似乎是大家的共识。你知道这是否已经成为最佳实践了吗？ - Gruber

@Gruber 首先，这是最易于实现的解决方案之一，只需最少的修改即可重用现有算法。这比发明和测试算法的新变体具有巨大优势，并且在性能方面成本几乎可以忽略不计。 - Óscar López

如果您想保留现有的二分查找，可以创建两个额外的数组，分别给出每个元素左侧和右侧相等值的数量。将它们用作组合键的一部分，您可以定位(key，left(0))和(key，right(0))——保存值key的第一个和最后一个元素。这可能只有在您需要单个值和计数时才值得，因为我猜如果您必须读取所有值，则移动左边和右边以找到它们的成本相对较小。 - mcdowella

Answer 9

以下是 Deril Raju（上面的答案中）提供的解决方案，移植到 Swift 中：

func bin_search(_ A: inout [Int], first: Int, last: Int, key: Int, searchLow: Bool) -> Int {
    var result = -1
    var low = first
    var high = last

    while low <= high {
        let mid = (low + high) / 2
        if A[mid] < key {
            low = mid + 1
        } else if A[mid] > key {
            high = mid - 1
        } else {
            result = mid
            if searchLow {
                high = mid - 1 // go on searching towards left (lower indices)
            } else {
                low = mid + 1 // go on searching towards right (higher indices)
            }
        }
    }
    return result
}

func bin_search_range(_ A: inout [Int], first: Int, last: Int, key: Int) -> (Int, Int) {
    let low = bin_search(&A, first: first, last: last, key: key, searchLow: true)
    let high = bin_search(&A, first: first, last: last, key: key, searchLow: false)
    return (low, high)
}


func test() {
    var A = [1, 2, 3, 3, 3, 4, 4, 4, 4, 5]

    assert(bin_search(&A, first: 0, last: A.count - 1, key: 3, searchLow: true) == 2)
    assert(bin_search(&A, first: 0, last: A.count - 1, key: 3, searchLow: false) == 4)
    assert(bin_search_range(&A, first: 0, last: A.count - 1, key: 3) == (2, 4))

    assert(bin_search(&A, first: 0, last: A.count - 1, key: 4, searchLow: true) == 5)
    assert(bin_search(&A, first: 0, last: A.count - 1, key: 4, searchLow: false) == 8)
    assert(bin_search_range(&A, first: 0, last: A.count - 1, key: 4) == (5, 8))

    assert(bin_search_range(&A, first: 0, last: A.count - 1, key: 5) == (9, 9))
    assert(bin_search_range(&A, first: 0, last: A.count - 1, key: 0) == (-1, -1))
}

test()

- rudifa

Answer 10

你的二分查找返回元素还是元素所在的索引？你能获取索引吗？

由于列表已排序，所有匹配元素应该相邻出现。如果您可以从标准搜索中获取返回项的索引，则只需要从该索引向两个方向搜索，直到找到非匹配项。

- Colin D

---

使用索引是算法的核心，所以我已经掌握了它。谢谢。 - Gruber