Hallo,
Habe eine Aufgabe, in der ich für Binary Search eine count() Methode implementieren soll.
Mein Problem:
Ich verstehe die Aufgabe nicht so ganz..
Besser gesagt im Text die einzelnen Schritte nicht, die ich machen muss..
Der Code ist fertig nur die Count() Methode soll erstellt werden:
Das ist die Aufgabe:
Implement a method count(int key) that returns the number of elements equal to the key. Then we can state: if i and j are the values returned by rank(int key) and count(int key) respectively, then a[i ... i+j-1] are the values in the array that are equal to key.
Ich bin mir überhaupt nicht sicher ob mein Ansatz annährend richtig ist, aber trotzdem habe ich eine Frage:
kann ich bei der Count() Methode 2 for-Schleifen für i und j erstellen und anschliessend die beiden miteinander vergleichen?
Das ist der Code:
Habe eine Aufgabe, in der ich für Binary Search eine count() Methode implementieren soll.
Mein Problem:
Ich verstehe die Aufgabe nicht so ganz..
Besser gesagt im Text die einzelnen Schritte nicht, die ich machen muss..
Der Code ist fertig nur die Count() Methode soll erstellt werden:
Das ist die Aufgabe:
Implement a method count(int key) that returns the number of elements equal to the key. Then we can state: if i and j are the values returned by rank(int key) and count(int key) respectively, then a[i ... i+j-1] are the values in the array that are equal to key.
Ich bin mir überhaupt nicht sicher ob mein Ansatz annährend richtig ist, aber trotzdem habe ich eine Frage:
kann ich bei der Count() Methode 2 for-Schleifen für i und j erstellen und anschliessend die beiden miteinander vergleichen?
Das ist der Code:
Java:
public class BinarySearch {
private int[] a;
public BinarySearch(int[] a) {
this.a = a;
}
/**
* Returns the index of the specified key in the specified array.
*
* @param key the search key
* @param a the array of integers, must be sorted in ascending order
* @return index of key in array <tt>a</tt> if present; <tt>-1</tt> otherwise
*/
public int indexOf(int key) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// Key is in a[lo..hi] or not present.
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return -1;
}
public int rank(int key) {
return indexOf(key);
}
public int count(int key){
int ar[] = {1,4,2,0,5,3,7,9,8};
Arrays.sort(ar);
for(int number : ar){
System.out.println(number);
}
int search = 9;
int ret = Arrays.binarySearch(ar, search);
return ret;
}
}