在特定元素上查找排序数组的范围索引

Question

我正在处理集合排序的数组。任务是查找值的范围。

让我们假设我们有这个排序数组：

int[] array = {1,1,1,3,3,9,10}

示例我们必须为元素1找到范围- min和max。我们很快发现元素1的第一个索引为0，范围max为2。

现在我们知道，0到2之间的范围都有1。如果搜索的元素是3，我们看到这个范围是3-4，对于元素9，范围是6-6。

我曾经用线性搜索来做这件事，但是如果有更快的方法去做，我会听到吗？

Answer 1

您可以使用二进制搜索的两个版本找到最左边和最右边的位置：

int[] array = { 1, 1, 1, 3, 3, 9, 10 }
int value = ...

int leftmost(int min, int max)
{
    if (min == max) return min
    int mid = (min + max) / 2

    if (array[mid] < value) return leftmost(mid + 1, max)
    else return leftmost(min, mid)
}

int rightmost(int min, int max)
{
    if (min == max) return min
    int mid = (min + max + 1) / 2

    if (array[mid] > value) return rightmost(min, mid - 1)
    else return rightmost(mid, max)
}

只需用min=0和max=array.length-1打电话。时间复杂度是O(logn)。

您将得到这样的输出(0-based索引)：

value=1  -> left=0, right=2
value=3  -> left=3, right=4
value=9  -> left=5, right=5
value=10 -> left=6, right=6

Answer 2

二进制搜索会快得多。你可以了解一下这个这里

Answer 3

假设一个较大的数组使用二进制，然后是线性的。

根据数组的大小，更快的方法可能是线性的。如果您使用像您一样的7个数字数组重复进行此搜索，那么您将不会看到多少性能差异。事实上，它可能会慢一些。

但是，扩展这个数组，这样您就有了更多的数据，您最好先执行二进制搜索，然后执行线性搜索。

做一次，抓取范围的底部，然后做线性，以找到范围的终点。

您可以为端点执行另一个二进制操作，但随着时间的推移，这应该会平均为一个简单的线性函数。