Interessanterweise ist die binäre Suche mächtiger als man glaubt. Sie kann nicht nur den kleinsten Index eines Elements zurückliefern, sondern auch zeigen, an welcher Stelle ein Element, dass nicht in der Liste ist, es eingefügt werden muss. Sie muss nur richtig impelementiert werden.
[code=java]public static int binarySearch(int[] arr, int key) {
int index = binarySearch(arr, key, 0, arr.length - 1);
return arr[index] == key ? index : -1;
}
private static int binarySearch(int[] arr, int key, int lo, int hi) {
if (lo > hi) {
return lo;
} else {
int mid = lo + (hi - lo >> 1);
if (key <= arr[mid]) {
return binarySearch(arr, key, lo, mid - 1);
} else {
return binarySearch(arr, key, mid + 1, hi);
}
}
}[/code]
Hier habe ich sie mal mit Rekursion modelliert mit der oben genannten "Erweiterung".
Jetzt brauchst du nur noch Zählen, was jetzt ziemlich einfach geworden ist, da du ja den ersten Index erhälst (Pseudocode):
[code]def count(arr : int[], key : int) : int {
var firstIndex = binarySearch(arr, key);
if(firstIndex == -1) return 0;
var sum = 0;
while(firstIndex < length(arr) & arr[firstIndex++] == key) sum ++;
return sum;
}[/code]
Dann erhälst du, wie in der Aufgabe gestellt i und j so, dass arr[binarySearch ... binarySearch + count - 1] == key hält.
