对具有重复项的排序数组使用二进制搜索

Question

我的任务是创建一个方法，该方法将打印在排序数组中找到值x的所有索引。

我知道，如果我们仅从0到N（数组的长度）对数组进行扫描，则最坏情况下的运行时间为O（n）。由于将对传递给该方法的数组进行排序，因此我假设我可以利用二进制搜索的优势，因为这将是O（log
n）。但是，这仅在数组具有唯一值的情况下有效。因为二进制搜索将在特定值的第一个“查找”之后完成。我当时正在考虑进行二进制搜索，以便在排序后的数组中找到x，然后检查该索引之前和之后的所有值，但是如果数组包含所有x值，那么看起来并不会更好。

我想我要问的是，有没有一种更好的方法可以找到比O（n）更好的排序数组中特定值的所有索引？

public void PrintIndicesForValue42(int[] sortedArrayOfInts)
{
    // search through the sortedArrayOfInts

    // print all indices where we find the number 42. 
}

例如：sortedArray = {1、13、42、42、42、77、78}将输出：“在索引处找到42：2、3、4”

Answer 1

好吧，如果您确实有一个排序数组，则可以进行二进制搜索，直到找到您要查找的索引之一为止，然后从那里容易找到其余的索引，因为它们都紧挨着每个索引，其他。

找到第一个实例后，便要找到它之前的所有实例，然后再找到它之后的所有实例。

使用该方法，您应该大致得到 O（lg（n）+ k） ，其中 k 是您要搜索的值的出现次数。

编辑：

而且，不，您将永远无法在少于 O（k）* 时间的时间内访问所有 k个 值。 *

第二次编辑： 这样，我可以感觉到自己实际上正在贡献一些有用的东西：

不仅可以搜索X的第一个和最后一个出现，还可以对第一个出现进行二进制搜索，然后对最后一个出现进行二进制搜索。这将导致总数为 O（lg（n））
。完成此操作后，您将知道所有索引之间也都包含X（假设已排序）

您可以通过搜索值是否等于 x ， 并 检查左侧（或右侧，取决于您要查找的是第一个还是最后一个）来确定值是否等于 x 。