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

Question

我正在使用对集合进行排序的数组。任务是找到一个值的范围。

假设我们有这个排序数组:

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

例子我们必须找到元素 1 的范围最小值和最大值。我们很快发现元素 1 的第一个索引为 0，范围最大值为 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