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