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

duplicates binary-search java

2022-09-01 15:00:21

我的任务是创建一个方法，该方法将打印在排序数组中找到值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”

答案 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);
        }
    }
}

答案 2

好吧，如果你确实有一个排序数组，你可以做一个二进制搜索，直到你找到你要找的索引之一，从那里，其余的应该很容易找到，因为它们都彼此相邻。

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

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

编辑：

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

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

您可以对第一个匹配项执行二进制搜索，并对最后一个实例执行二进制搜索，而不是只搜索第一个匹配项和最后一个匹配项执行二进制搜索。这将导致O（lg（n））总计。完成此操作后，您将知道索引之间的所有索引也包含X（假设它是排序的）

为此，您可以搜索检查值是否等于 x，然后检查左侧（或右侧的值，具体取决于您查找的是第一次出现还是最后一次出现）是否等于 x。