这个findRange方法的大O.

问题描述

我正在试图弄清楚下面显示的findRange的运行时复杂性，它找到了排序数组a和密钥的底部和顶部索引。

如果找不到密钥则返回 - 1 -1。



int [] a = new int [] {1,2,3,3,5,5,5,5};

findRange（a，5）=> 5 8



我想出解决方案O（2 * log（#times_key_appears）* log n）=> O（（log n）^ 2）

这是正确的吗？

那里有更好的算法解决方案吗？

I'm trying to figure out the runtime complexity of findRange shown below, which finds the bottom and top index given a sorted array a and key key.
If key is not found then return -1 -1.

int[] a = new int[] { 1, 2, 2, 3, 3, 5, 5, 5, 5 };
findRange(a, 5) => 5 8

I'm coming up with the solution O(2 * log(#times_key_appears)* log n) => O((log n)^2)
Is this correct?
Is there a better algorithmic solution out there?

public void findRange(int[] a, int key) {
    int bsLeft = bsLeft(a, 0, a.length , key, -1);
    System.out.print(bsLeft);
    System.out.print(" ");
    System.out.println(bsRight(a, bsLeft, a.length , key, -1));
}

public int bsLeft(int[] a, int startIndex, int lastIndex, int key, int found){
    int value = Arrays.binarySearch(a, startIndex, lastIndex, key);
    if (value < 0) {
        return found;
    }
    return bsLeft(a, startIndex, value -1, key, value);
}

public int bsRight(int[] a, int startIndex, int lastIndex, int key, int found){
    int value = Arrays.binarySearch(a, startIndex , lastIndex, key);
    if (value < 0) {
        return found;
    }
    return bsRight(a, value + 1, lastIndex, key, value);
}

推荐答案

这篇关于这个findRange方法的大O.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！