使用带有重复的排序数组的二分搜索
我的任务是创建一个方法，该方法将打印在排序数组中找到值 x 的所有索引.
I've been tasked with creating a method that will print all the indices where value x is found in a sorted array.
我知道，如果我们只是从 0 到 N(数组长度)扫描数组，最坏的情况下运行时间为 O(n).由于将传递给方法的数组将被排序，我假设我可以利用使用二进制搜索，因为这将是 O(log n).但是，这仅适用于数组具有唯一值的情况.因为二进制搜索将在第一次找到"特定值之后完成.我正在考虑进行二进制搜索以在已排序的数组中找到 x，然后检查该索引之前和之后的所有值，但是如果数组包含所有 x 值，它似乎不会好得多.
I understand that if we just scanned through the array from 0 to N (length of array) it would have a running time of O(n) worst case. Since the array that will be passed into the method will be sorted, I'm assuming that I can take advantage of using a Binary Search since this will be O(log n). However, this only works if the array has unique values. Since the Binary Search will finish after the first "find" of a particular value. I was thinking of doing a Binary Search for finding x in the sorted array, and then checking all values before and after this index, but then if the array contained all x values, it doesn't seem like it would be that much better.
我想我要问的是，有没有比 O(n) 更好的方法来找到排序数组中特定值的所有索引?
I guess what I'm asking is, is there a better way to find all the indices for a particular value in a sorted array that is better than 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 was found at Indices: 2, 3, 4"
Ex: sortedArray = { 1, 13, 42, 42, 42, 77, 78 } would print: "42 was found at Indices: 2, 3, 4"
推荐答案
好吧，如果你确实有一个排序数组，你可以进行二分搜索，直到找到你要查找的索引之一，然后从那里，其余的应该很容易找到，因为它们都彼此相邻.
Well, if you actually do have a sorted array, you can do a binary search until you find one of the indexes you're looking for, and from there, the rest should be easy to find since they're all next to each-other.
一旦你找到了你的第一个实例，你就会去寻找它之前的所有实例，然后是它之后的所有实例.
once you've found your first one, than you go find all the instances before it, and then all the instances after it.
使用该方法，您应该大致得到 O(lg(n)+k)，其中 k 是您要搜索的值的出现次数.
Using that method you should get roughly O(lg(n)+k) where k is the number of occurrences of the value that you're searching for.
而且，不，您将永远无法在不到 O(k) 的时间内访问所有 k 值.
And, No, you will never be able to access all k values in anything less than O(k) time.
第二次让我觉得我实际上在贡献一些有用的东西:
Second edit: so that I can feel as though I'm actually contributing something useful:
除了搜索 X 的第一次和最后一次出现之外，您还可以对第一次出现进行二进制搜索，对最后一次出现进行二进制搜索.这将导致 O(lg(n)) 总数.一旦你这样做了，你就会知道所有的索引之间也包含 X(假设它是排序的)
Instead of just searching for the first and last occurrences of X than you can do a binary search for the first occurence and a binary search for the last occurrence. which will result in O(lg(n)) total. once you've done that, you'll know that all the between indexes also contain X(assuming that it's sorted)
您可以通过搜索检查值是否等于 x ，AND 检查值是否在左侧(或右侧，具体取决于您是否在查看对于第一次出现或最后一次出现)等于 x.
You can do this by searching checking if the value is equal to x , AND checking if the value to the left(or right depending on whether you're looking for the first occurrence or the last occurrence) is equal to x.
相关文章