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

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)的结果

public static void PrintIndicesForValue(int[] numbers, int target) {
    if (numbers == null)
        return;

    int low = 0, high = numbers.length - 1;
    // get the start index of target number
    int startIndex = -1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (numbers[mid] > target) {
            high = mid - 1;
        } else if (numbers[mid] == target) {
            startIndex = mid;
            high = mid - 1;
        } else
            low = mid + 1;
    }

    // get the end index of target number
    int endIndex = -1;
    low = 0;
    high = numbers.length - 1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        if (numbers[mid] > target) {
            high = mid - 1;
        } else if (numbers[mid] == target) {
            endIndex = mid;
            low = mid + 1;
        } else
            low = mid + 1;
    }

    if (startIndex != -1 && endIndex != -1){
        for(int i=0; i+startIndex<=endIndex;i++){
            if(i>0)
                System.out.print(',');
            System.out.print(i+startIndex);
        }
    }
}

Answer 2

好吧,如果你确实有一个排序数组,你可以进行二进制搜索,直到你找到一个你正在寻找的索引,从那里,其余的应该很容易找到,因为它们都在每个旁边 - 其他.

一旦你找到了第一个,你就会找到它之前的所有实例,然后找到它之后的所有实例.

使用该方法,您应该大致得到O(lg(n)+ k),其中k是您要搜索的值的出现次数.

编辑:

而且,不,你永远无法在O(k)时间内访问所有k值.

第二次编辑:这样我觉得好像我实际上贡献了一些有用的东西:

而不是只搜索X的第一次和最后一次出现,而不是搜索第一次出现的二进制搜索和最后一次出现的二进制搜索.这将导致总计O(lg(n)).一旦你完成了,你会知道所有索引之间也包含X(假设它已经排序)

您可以通过搜索检查是否值等于做X,和如果(取决于你是否正在寻找第一次出现或最后出现的或右)的值向左检查等于X.