# Anzahl gleicher Elemente in Array



## Kabauter (29. Mrz 2017)

Hallo,
wie kann ich in einem sortierten Array die Anzahl gleicher Elemente möglichst schnell (Binäre Suche) herausfinden? In dem Beispiel also die Anzahl von 5 in einem int-array.
Normalerweise (ohne binäre Suche) sieht der Code so aus:


```
for (int i = 0; i < array.length; i++) {
    if (array[i]==5) {   
        anzahl++;
    }
}
```


----------



## mrBrown (29. Mrz 2017)

Ich würde den höchsten und niedrigsten Index für die 5 suchen, damit hast du ja dann auch die anzahl


----------



## Kabauter (29. Mrz 2017)

Das hatte ich mir auch so gedacht, nur fällt mir dazu kein passender Code ein 
Hatte den Array in zwei Teile geteilt und so jeden Teil durchsucht, allerdings komme ich dann mit dem finden des ersten Elements nicht mehr klar. 
tmp soll hier den kleinsten Index, der die 5 enthält, darstellen

```
while (links < rechts) {
         int mid = (links+rechts) / 2;
         if (array[mid] == 5)
             tmp=middle;
         else if (array[mid] > 5)
             rechts = mid - 1;
         else
             links = mid + 1;
         }
}
```


----------



## Xyz1 (29. Mrz 2017)

Ist n/2 nicht schnell genug?


----------



## Kabauter (29. Mrz 2017)

DerWissende hat gesagt.:


> Ist n/2 nicht schnell genug?



Nein leider nicht, es soll in log(n) gesucht werden.


----------



## Xyz1 (30. Mrz 2017)

Kabauter hat gesagt.:


> Nein leider nicht, es soll in log(n) gesucht werden.



Also, ich weiß zwar nicht, why ich mir das antue, aber es kann in log(n) herausgefunden werden, wie oft eine Zahl n im (sortiert) Array enthalten ist, dabei steht 0 == nicht enthalten:

```
// main method...
        for (int i = 0; i < 10; i++) {
            int[] ia = rando.ints(5, 0, 2).toArray();
            Arrays.sort(ia);
            System.out.println(Arrays.toString(ia));
            System.out.println(findNotNCount(ia, findIndex(ia, 0)));
            System.out.println(findNotNCount(ia, findIndex(ia, 1)));
            System.out.println("");
        }

    }

    /**
     * n/2....
     *
     * @param array
     * @param n
     * @return
     */
    static int findNaiv(int[] array, int n) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == n) {
                for (int j = i + 1; j < array.length; j++) {
                    if (array[j] != n) {
                        return j - i;
                    }
                }
                return array.length - i;
            }
        }
        return 0;
    }

    /**
     * log(n)..
     * @param array
     * @param n
     * @return
     */
    static int findIndex(int[] array, int n) {
        int i = 0, j = array.length - 1, k = i + (j - i) / 2;
        while (i <= j) {
            if (array[k] < n) {
                i = k + 1;
                k = i + (j - i) / 2;
            } else if (array[k] > n) {
                j = k - 1;
                k = i + (j - i) / 2;
            } else {
                return k;
            }
        }
        return -1;
    }

    /**
     * log(n)..
     * @param array
     * @param n
     * @return
     */
    static int findNotNCount(int[] array, int n) {
        int i = 0, j = n - 1, k = i + (j - i) / 2;
        while (i <= j) {
            if (array[k] == array[n]) {
                j = k - 1;
                k = i + (j - i) / 2;
            } else {
                i = k + 1;
                k = i + (j - i) / 2;
            }
        }
        if (k < 0) {
            return 0;
        }
        int a = k;
        i = n + 1;j = array.length - 1;k = i + (j - i) / 2;
        while (i <= j) {
            if (array[k] == array[n]) {
                i = k + 1;
                k = i + (j - i) / 2;
            } else {
                j = k - 1;
                k = i + (j - i) / 2;
            }
        }
        int b = k;
        return b - a;
    }
```

Ich muss aber gleich dazusagen, das es... unklug... ist, das auf ganze/volle 5 Elemente loszulassen; der Unterschied zu findNaiv macht sich vielleicht erst bei Tausenden von Elementen bemerkbar.

hth 

Aber hallo, was solls, ich habe auch etwas dabei gelernt. 

Bearbeitung: Ich habe die Ausgabe vergessen:

```
[1, 1, 1, 1, 1]
0
5

[0, 0, 0, 0, 1]
4
1

[0, 1, 1, 1, 1]
1
4

[0, 0, 0, 1, 1]
3
2

[0, 1, 1, 1, 1]
1
4

[0, 0, 0, 1, 1]
3
2

[0, 0, 0, 1, 1]
3
2

[0, 0, 0, 0, 1]
4
1

[0, 1, 1, 1, 1]
1
4

[0, 0, 1, 1, 1]
2
3
```

wenn man rando mit 4 initialisiert....


----------



## Jardcore (30. Mrz 2017)

@Offtopic:
@DerWissende : kauf dir mal https://www.amazon.de/Clean-Code-Handbook-Software-Craftsmanship/dp/0132350882
Kannst du mir erklären wozu du die Kommentare an den Methoden brauchst?

Das sollte der Standard weg sein, der an der Unit gelehrt wird.

```
public class BinarySearch { 
    public void searchBinary(int[] intArr, int anfang, int ende, int zahl) {   
        int grenze = anfang + ((ende - anfang) / 2); 
         
        if (intArr.length == 0) { 
            System.out.println("Array leer."); 
            return; 
        } 
         
        if (grenze >= intArr.length){ 
            System.out.println(zahl + " nicht im Array enthalten."); 
            return; 
        } 

        if (zahl > intArr[grenze]) { 
            searchBinary(intArr, grenze + 1, ende, zahl); 
        } else if (zahl < intArr[grenze] && anfang != grenze) { 
            searchBinary(intArr, anfang, grenze - 1, zahl); 
        } else if(zahl == intArr[grenze]) { 
            System.out.println(zahl + " an Position " + grenze + " enthalten."); 
        } else{ 
            System.out.println(zahl + " nicht im Array enthalten."); 
        } 
    } 

    public static void main(String[] args) { 
        int[] testArr = { 5, 3, 5, 228, 14, 69, 18, 27, 109, 85 }; 
        Arrays.sort(testArr); 
        BinarySearch bs = new BinarySearch(); 
        bs.searchBinary(testArr, 0, testArr.length - 1, 228); 
    } 
}
```
Zu finden unter:
https://javabeginners.de/Algorithmen/Suchalgorithmen/Binaere_Suche.php


----------



## Xyz1 (30. Mrz 2017)

Jardcore hat gesagt.:


> Das sollte der Standard weg sein, der an der Unit gelehrt wird.


Ja, der findige Fuchs (Student) kennt es am Ende des 1. Semesters. Den Anderen wird es später eingebläut.

aus der Praxis geht hervor, dass mehr als 1 Kommentar pro Methode unangebracht ist. (Methoden dürfen ja nicht beliebig lang werden.)

ABER 1. ist das eine rekursive Methode, 2. etwas langsamer, 3. entspricht das nicht der Aufgabenstellung, 4. sollte die Häufigkeit, mit der ein Element n vorkommt, ermittelt werden, 5. einfach einen Index eines Elements n zu ermitteln, ist nicht genug, 6. deine zwei Prüfungen, ob alle Parameter legal sind, braucht meine Methode *nicht* (das wird inklusiv geprüft).

Dennoch Danke, dass du nochmal die Basics aufzeigst.


----------



## mrBrown (30. Mrz 2017)

DerWissende hat gesagt.:


> aus der Praxis geht hervor, dass mehr als 1 Kommentar pro Methode unangebracht ist. (Methoden dürfen ja nicht beliebig lang werden.)


Deine Kommentare sind trotzdem Bullshit.


----------



## Jardcore (30. Mrz 2017)

DerWissende hat gesagt.:


> */**
> * n/2....
> *
> * @param array
> ...


Kannst du mir erklären, welchen Mehrwert dieser Kommentar hat? Was ist array, was ist n, was ist der Return-Wert?



Jardcore hat gesagt.:


> Das sollte der Standard weg sein, der an der Unit gelehrt wird.


Meine natürlich Uni


----------



## Xyz1 (30. Mrz 2017)

Jardcore hat gesagt.:


> Kannst du mir erklären, welchen Mehrwert dieser Kommentar hat? Was ist array, was ist n, was ist der Return-Wert?


Ich war zu faul, an den drei Stellen etwas (sinnvolles) einzutragen. Also hab ich es leergelassen. My fault.


----------



## Senftube (1. Apr 2017)

Hallo,
schön binarySearch() selbst zu implementieren (dann hat man es auch verstanden)
aber es gibt doch java.util.Arrays.binarySearch() mit zahllosen Überladungen, sodass man auch
sortierte arrays mit eigenen Klassen durchsuchen kann, indem man als 3. Parameter einen Comperator
übergibt.
Leider kannst du die Haeufigkeit eines Wertes nicht mit der binarySearch() methode ermitteln. Wenn es einen Wert mehrfach gibt ist die gelieferte Position/Index je nach der Position des Wertes der zuerst geprüft wird ehr zufällig. Wenn der Wert noch nicht enthalten ist, bekommt man die Position abzüglich -1 wo man den noch
unbekannten Wert im Array aufnehmen müsste, damit die Liste sortiert bleibt.Also wenn -1 geliefert wird muss auf Pos 0 eingefügt werden, bei -3 an der Stelle 2.

Ich würde das so lösen:

```
public static countValue(int[] array_sorted,int val)
{   
    int cnt=0; int i=0;
    for (i=0;i < array_sorted.length;i++)
    {
        if (array_sorted[i] == val)
        {
            cnt++; // jetzt nachfolgende werte untersuchen
            for (int k=i+1;k < array_sorted.length;k++)
            { if (array_sorted[k] != val) return cnt;
              cnt++;
            }
        }       
    }
    return cnt;
}
```


----------



## mrBrown (1. Apr 2017)

Senftube hat gesagt.:


> Ich würde das so lösen:


Der Code ist vom Stil her aber schon echt unschön und umständlich...


----------



## Meniskusschaden (1. Apr 2017)

Ausserdem wurde für die Suche O(log n) gefordert.


----------



## Xyz1 (1. Apr 2017)

Außerdem macht das mein naiver Zählalgorithmus findNaiv bereits (damit (später) evtl. die Laufzeiten vergleichen werden können)...
Außerdem hab ich schon mit eine der besten Implementierungen hingeklatscht...
Soll nicht unfreundlich klingen, aber ich habe mir schon Mühe gegeben.^^


----------



## Xyz1 (1. Apr 2017)

Aber `findNotNCount` ist echt unleserlich... ich sollte zwischendurch auf vernünftige Namensgebung usw.
----
Hallo aber, wenn es (unwahrscheinlich) den Algorithmus noch nicht gab, bin ich der Autor - und keiner darf ihn verwenden.  (Sehr unwahrscheinlich)


----------



## JStein52 (1. Apr 2017)

DerWissende hat gesagt.:


> Hallo aber, wenn es (unwahrscheinlich) den Algorithmus noch nicht gab, bin ich der Autor - und keiner darf ihn verwenden.


Mhmmm, rekursive Algorithmen neigen dazu bei grösseren Rekursionstiefen mal mit StackOverflow ins Gras zu beissen.


----------



## Senftube (1. Apr 2017)

Meniskusschaden hat gesagt.:


> Ausserdem wurde für die Suche O(log n) gefordert.



Wäre als Kompromiss zwischen n/2 und log(n) wenn man die Sortiertheit ausnutzen will und nicht das
ganze Array absuchen will. Wenn man von einer Normalverteilung der Werte ausgeht, kann man entscheiden, ob man den Wert von vorne oder von hinten im Array sucht.


----------



## Xyz1 (1. Apr 2017)

(Er ist doch gar nicht rekursiv...) Ihr könnt das ja mal testen:

```
public static void main(String[] args) {
        Random rando = new Random(4);
        long t1 = 0, t2 = 0, t3 = 0;
        for (int i = 5_000; i < 10_000_000; i++) {
            int[] ia = rando.ints(i, 0, 3).toArray();
            Arrays.sort(ia);
            t1 = System.currentTimeMillis();
            int n1 = findNaiv(ia, 0);
            t2 = System.currentTimeMillis();
            int n2 = findNotNCount(ia, findIndex(ia, 0));
            t3 = System.currentTimeMillis();
            System.gc();
            System.out.println("i  = " + i);
            System.out.println("n1 = " + n1);
            System.out.println("n2 = " + n2);
            System.out.println(t2 - t1);
            System.out.println(t3 - t2);
            System.out.println("----");
            if (t2 - t1 > t3 - t2) {
                break;
            }
        }
    }
```

Das Programm läuft bei mir ca. 1 Minute und hält bei ca. 15_000 an.

Das Programm wird immer irgendwann anhalten (auch ohne Abbruchbedingung)!!!! Da es unterschiedliche Laufzeiten sind.

`System.gc` ist da, damit das vorherige Array 'aufgeräumt' wird.

Dann ein Fazit noch.... Es ist sinnvoll, diesen Algorithmus bei Elementen > 15_000 anzuwenden. Mir fällt aber keine Anwendung ein, in der es sinnvoll ist, >= 5_000mal dasselbe Element zu haben.


----------



## mrBrown (1. Apr 2017)

Senftube hat gesagt.:


> Wäre als Kompromiss zwischen n/2 und log(n) wenn man die Sortiertheit ausnutzen will und nicht das
> ganze Array absuchen will. Wenn man von einer Normalverteilung der Werte ausgeht, kann man entscheiden, ob man den Wert von vorne oder von hinten im Array sucht.


Das ist kein Kompromiss, das ist die quasi die Ursprungslösung mit stumpfem durchlaufen in hässlich.


----------



## mrBrown (1. Apr 2017)

DerWissende hat gesagt.:


> System.gc ist da, damit das vorherige Array 'aufgeräumt' wird.


Verbreite doch nicht immer diesen Unsinn mit händisch System.gc nutzen wäre irgendwie sinnvoll...



DerWissende hat gesagt.:


> Dann ein Fazit noch.... Es ist sinnvoll, diesen Algorithmus bei Elementen > 15_000 anzuwenden. Mir fällt aber keine Anwendung ein, in der es sinnvoll ist, >= 5_000mal dasselbe Element zu haben.


Wäre in der heutigen Zeit auch ein ziemliches Wunder, wenn man plötzlich viele Daten hätte.


----------



## Meniskusschaden (1. Apr 2017)

Senftube hat gesagt.:


> Wäre als Kompromiss zwischen n/2 und log(n) wenn man die Sortiertheit ausnutzen will und nicht das
> ganze Array absuchen will. Wenn man von einer Normalverteilung der Werte ausgeht, kann man entscheiden, ob man den Wert von vorne oder von hinten im Array sucht.


Das ändert aber nichts daran, dass dein Algorithmus für die Suche O(n) benötigt.


----------



## JStein52 (1. Apr 2017)

DerWissende hat gesagt.:


> (Er ist doch gar nicht rekursiv...)


Entschuldigung, stimmt. Das war ja gar nicht von dir.


----------



## Xyz1 (1. Apr 2017)

mrBrown hat gesagt.:


> Verbreite doch nicht immer diesen Unsinn mit händisch System.gc nutzen wäre irgendwie sinnvoll...
> 
> Wäre in der heutigen Zeit auch ein ziemliches Wunder, wenn man plötzlich viele Daten hätte.


gc: Ok, man müsste ihm noch 100 Millisekunden Zeit geben, damit es sinnvoll ist. Ich habe ja auch nicht behauptet, dass dieser Benchmark perfekt sei.... Aber theoretisch läufts nicht ewig 

Daten: Ok, bei DNA vielleicht, dann machts wiederum keinen Sinn, erst zu sortieren, dann zu zählen - anstatt einmal drüber zu laufen.

Das Szenario ist einfach nicht sinnvoll denkbar.

Außerdem.... Evtl. auf anderen nicht Beschimpfungen an den Kopf hauen, ich denke mal, viele sind einfach in der Lernphase.

Alle Hintergründe dazu werden in einer Komplexitätstheorievorlesung ausführlich behandelt


----------



## mrBrown (1. Apr 2017)

DerWissende hat gesagt.:


> gc: Ok, man müsste ihm noch 100 Millisekunden Zeit geben, damit es sinnvoll ist. Ich habe ja auch nicht behauptet, dass dieser Benchmark perfekt sei.... Aber theoretisch läufts nicht ewig


Ganz ehrlich: sag besser nie mehr was zu System.gc, da kommt nur Unsinn raus.



DerWissende hat gesagt.:


> Daten: Ok, bei DNA vielleicht, dann machts wiederum keinen Sinn, erst zu sortieren, dann zu zählen - anstatt einmal drüber zu laufen.
> 
> Das Szenario ist einfach nicht sinnvoll denkbar.


Dir fällt ersthaft nur DNA ein zu Daten mit mehr als 5000 "gleichen" Elementen? Ich kann mir kaum Datenverarbeitung mit weniger als tausenden Elementen vorstellen...


----------



## Meniskusschaden (1. Apr 2017)

DerWissende hat gesagt.:


> Das Szenario ist einfach nicht sinnvoll denkbar.


Man könnte es benutzen, wenn man ein Array sämtlicher EU-Bürger hätte und ausrechnen möchte, was es kosten würde, jedem 18jährigen ein Interrail-Ticket zu schenken. Aber auf so eine Idee würde wohl niemand kommen.


----------



## Xyz1 (1. Apr 2017)

Soooo - genug gepöbelt, ich Feierabend für heute.


----------



## Senftube (2. Apr 2017)

Vielleicht so:

```
public static int countValue(int[] arr,int val)
{
    int cnt=0;
    int pos = Arrays.binarySearch(arr,val);
    if (pos < 0) return cnt;
    cnt++;
    // benachbarte werte ober- und unterhalb pos untersuchen
    for (int i=pos-1;i >= 0;i--) // unterhalb
    {
        if (arr[i] != val) break;
        cnt++;
    }
    for (int i=pos+1;i < arr.length;i++) // oberhalb
    {
        if (arr[i] != val) break;
        cnt++;
    }
    return cnt;
}
```


----------



## Xyz1 (2. Apr 2017)

Yeah, nur dass das nicht log(n) ist 
Lass es doch einfach, das Verlangte steht ja schon oben. 
----
Oder Übungszwecke, dann will ich nichts gesagt haben...


----------



## Meniskusschaden (2. Apr 2017)

DerWissende hat gesagt.:


> Yeah, nur dass das nicht log(n) ist


Eigentlich doch. Oder genauer O(log(n)+m), wenn m die Anzahl gleicher Elemente ist. Die logarithmische Laufzeit war aber nur für die Suche gefordert.


----------



## mrBrown (2. Apr 2017)

Meniskusschaden hat gesagt.:


> Eigentlich doch. Oder genauer O(log(n)+m), wenn m die Anzahl gleicher Elemente ist. Die logarithmische Laufzeit war aber nur für die Suche gefordert.


naja, angenommen m wächst ähnlich wie n: `O(log(n)+m) = O(log(n)+n/x) = O(log(n)+n) = O(n)`


----------



## Meniskusschaden (2. Apr 2017)

mrBrown hat gesagt.:


> naja, angenommen m wächst ähnlich wie n: O(log(n)+m) = O(log(n)+n/x) = O(log(n)+n) = O(n)


Ja, das ist der worst case, beispielsweise wenn sämtliche Elemente gleich sind. Es kann aber nicht viele Zahlen geben, die fast n-mal im Array vorkommen. Im Durchschnitt wird es also schneller sein, es sei denn, man fragt immer wieder diese Zahl ab. Ich glaube, das wäre wirklich kein realistisches Szenario mehr.


----------



## Meniskusschaden (2. Apr 2017)

Andererseits würde ich @DerWissende und @mrBrown jetzt doch zustimmen, weil man ja binär weiter suchen könnte, bis man das erste und letzte Vorkommen der Zahl gefunden hat. Das wäre dann auch im worst case O(n).


----------

