Aus einem Array die nächst größere Zahl

Hallo,

ich bin neu hier, lese aber schon seit einiger zeit mit.

also ich habe eine liste mit zahlen in einem double Array gespeichert. Nun soll etwas ausgerechnet werden und das Ergebnis davon Soll mit den zahlen im Array verglichen werden und die nächst größere zahl heraus gepickt werden. Ansich kein problem aber mir ist das mit If/Else ElseIf zu umständlich. Switch, Case funktioniert ja mit double nicht, gibt es eine elegantere Methode das zu lösen als ich es bisher mit If, Else mache ?

mfg

Hallo NameIt,

hast du ein Code Beispiel von dir wie du es bisher gelöst hast, oder es versucht hast zu lösen?!
Ansonsten wird schwer dir zu helfen ......
Hab nämlich nicht wirklich genau verstanden was du meinst ....

Greetz da kubi.

Hallo NameIt,

wieso ist das if schwierig? Du bauchst ja nicht mal ein else. Schon gar kein else if.

Natürlich gehe ich davon aus, dass du eine Schleife verwendest.

herbivore

Natürlich gehe ich davon aus, dass du eine Schleife verwendest.

Da hätten wir das Problem, ich bin mal wieder getreu dem Motto: "Warum einfach wenn es auch schwer geht?" hinterher gewesen.

Trotzdem, danke für die schnellen antworten.

kannst du das array nicht mit einen bubblesort sortieren bzw mit einer funktion und dann steht ja die größte bzw kleinste zahl ganz vorne, dann kannst du ja nach belieben deine zahlen rauspicken weisst aber immer wo deine größte zahl ist

oder versteh ich dich da falsch ?

gruß radix

Darf ich eine alternative Herangehensweise vorschlagen, ohne das Rad (bzw den Sortieralgorithmus) neu zu erfinden?

double ergebnis = myArray.OrderBy(p => p).FirstOrDefault(p => p > meineBerechnung());

Gruß, LaTino

@radix,
warum erst aufwändig einen langsamen Sortieralgorithmus implementieren, wenn es bereits Array.Sort gibt?

Zu beachten beim Umgang mit Float oder Double, keine Ist-gleich-Vergleiche. Näheres unter [FAQ] Double und Float: Fehler beim Vergleich und Rundungsfehler

Warum überhaupt erst sortieren, wenn man einfach linear durch die Liste geht und den größten Wert sich merkt?

Warum nicht einfach

double derHoechsteWertimArray = array.Max(p => p);

Weil der OP den kleinsten Wert des Arrays möchte, der größer als eine gegebene Zahl ist.

LaTino

Warum überhaupt erst sortieren, wenn man einfach linear durch die Liste geht und den größten Wert sich merkt?

In einem Sortierten Array einen (bestimmten) Wert suchen ist performanter als in einem unsortierten Array.
Wiki: Binäre Suche

Weil der OP den kleinsten Wert des Arrays möchte, der größer als eine gegebene Zahl ist.

Dann bringt es natürlich nichts 🙂

In einem Sortierten Array einen (bestimmten) Wert suchen ist performanter als in einem unsortierten Array.

Das mag ja sein. Aber man muss gar nicht suchen. Wenn ich herbivore richtig verstehe, meinte er das mit seinem Posting.

/* double[] myList; */
double tmpResult = DoCalculation();
double result = myList[0];
for(int i = 0; i < myList.Length; i++)
{
  if(myList[i] > tmpResult && myList[i] < result)
    result = myList[i];
}

return result;

Keine Suche. Kein Sortieren. Nix. Ich find die Linq-Variante dennoch schöner 😉.

LaTino

Keine Suche.

Was ist es denn?

Und genau so meinte ich es.

Okay, vielleicht bin ich da haarspalterisch.
Suche => Ergebnis ist bekannt, aber nicht, welches Element aus der Suchmenge dem Ergebnis entspricht (Suche nach "Martin" in einer Liste von Namen. Suche nach "07543" in der Postleitzahlendatenbank).

Das da ist keine Suche in diesem Sinn. "Auswahl, Vergleich, Zuweisung" würd ich das eher nennen 😉.

Wie dem auch sei. Dürfte vom Rechenaufwand der das minimalste Vorgehen sein.

LaTino

Aber man muss gar nicht suchen

Doch, du suchst in einem Array die kleinste Zahl, die größer als die übergebene Zahl ist. Dies geht entweder wie du es machst, wo du jede Zahl prüfst, ob sie die gesuchte Zahl ist oder du mittels binärer Suche wo du den Aufwand auf log2n beschränkst (statt linearer Aufwand).

Noch etwas performanter dürfte in diesem Bereich die Interpolationssuche sein, diese ist vergleichbar mit einem Nachschlagen eines Wortes im Duden, wo ich bei einem Wort was mit Z anfängt nicht erst von A bis Y durchrattern muss, oder wie bei der binären Suche ab M anfangen muss, sondern direkt weit hinten meinen Ausgangspunkt habe.

Aber man muss gar nicht suchen
du mittels binärer Suche wo du den Aufwand auf log2n beschränkst (statt linearer Aufwand).

Bitte auch den Sortieraufwand mit in die Rechnung einbeziehen.

LaTino

Bitte auch den Sortieraufwand mit in die Rechnung einbeziehen.

Der Sortieraufwand relativiert sich, mit der Anzahl der Aufrufe der Funktion. Klar wenn ich diese Funktion nur nur einmal brauche, ist ein Sortieren und anschließendes Suchen langsamer als direkt das Array von 0 bis n durchzulaufen. Brauchst du funktion mehrmals (ab 2 oder 3 mal) ist ein Sortieren und das Suchen auf dem sortierenten Array in jedem Fall günstiger.

Letzter Senf von mir dazu:

a) der Aufwand der Methode, die du vorschlägst, ist P(n,m) = R(n)/m + O(n) = R(n)/m + log2n mit m Anzahl der Laeufe und n Groesse des Arrays. Der Algorithmus von mir hat S(n,m) = mn. Dein Algorithmus ist daher effizienter für R(n) < mn, oder auf deutsch: wenn dein Sortieralgothmus jedes Element weniger als m-Mal anfasst, bist du im m-ten Durchlauf effizienter. Für m = 1 bist du in jedem Fall ineffizienter, weil es meines Wissens keinen Sortieralgorithmus mit R(n) < n gibt.

b) obige Aussage gilt nur für unveränderliche Arrays. Für veränderliche ist ein linearer einmaliger Durchlauf IMMER effizienter. Ich vermute die Wahrscheinlichkeit, dass es sich bei einem Array von double-Zahlen um eine Sammlung fester Werte handelt, bei weniger als 1%. Auf deutsch: Für das ursprünglich gepostete Problem ist eine binäre Suche daher vermutlich die am wenigsten geeignete Variante.

Gruß,

LaTino

Noch etwas Senf von mir

Ich find die Linq-Variante dennoch schöner 😉.

Meine alternative Linq-Variante:

const int min = 6;
int[] werte = new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
// Bei nicht vorhandsein wird eine InvalidOperationException geworfen
werte.First(p => p > min);
// Gibt bei nicht vorhandsein den Defaultwert (hier 0) zurück
Console.WriteLine(werte.FirstOrDefault(p => p > min));

Geht doch auch ohne ein simuliertes ordnen

Noch etwas Senf von mir
Geht doch auch ohne ein simuliertes ordnen

Ja. Wenn man ein sortiertes Array hat, muss man natürlich nicht sortieren. Hast du deinen Code schon mit int[] test = new int[] { 45,3,4,7,2,5,8,23,12 }; versucht?

LaTino

Man kann ja auch Array.Sort(werte); aufrufen.
Wenn man das nicht will bleibt immer noch

werte.Min(p => Math.Abs(p - min) + min);

Array.Sort(werte);
var output = werte.First(p => p > vergleich)

und

var output = werte.OrderBy(p => p).First(p => p > vergleich)

Erklärst du mir den Unterschied? Ich verstehe ihn nicht. Ich verstehe auch nicht, wie sich "Array.sort" mit deiner Aussage, es gehe auch ohne simuliertes Ordnen, verträgt. Und mich interessiert, was du machst, wenn du die ursprüngliche Reihenfolge der Zahlen eigentlich noch brauchst.

Dein zweiter Vorschlag (min) liefert für:
array(1,2,3,5,8,13,21,34) und Vergleichswert 6 das Minimum folgenden Arrays:
compare_array(11,10,9,7,8, 20, 36, 62), also 7. Dieser Wert war im urspruenglichen array nicht einmal vorhanden.

Ich halt jetzt wirklich meine Klappe, versprochen. PM gibt's ja auch noch 😃.

LaTino

Wow eine menge input, schon mal vielen dank dafür da muss ich mich mal rein lesen. Aber ich hatte es längst gelöst, hätte ich wahrscheinlich schreiben sollen, ich dachte eigentlich das wäre ersichtlich. Na ja, ich hab es so gelöst:

 for (int i = 0; i <= liste.Length; i++)
                        {
                            if (widerstand <= liste[i])
                            {
                                nwiderstand = liste[i];
                                break;

das war schon die ganze zauberei...

  
  
/* double[] myList; */  
double tmpResult = DoCalculation();  
double result = myList[0];  
for(int i = 0; i < myList.Length; i++)  
{  
  if(myList[i] > tmpResult && myList[i] < result)  
    result = myList[i];  
}  
  
return result;  
  

funktioniert aber auch nicht, weil du result mit double.MaxValue vorinitialisieren solltest, ansonsten knallt es sofort, wenn myList[0] < tmpResult ist.

for (int i = 0; i <= liste.Length; i++)  
                        {  
                            if (widerstand <= liste[i])  
                            {  
                                nwiderstand = liste[i];  
                                break;  

Hm, der Algorithmus macht mal gänzlich was anderes, er findet nämlich den erstbesten Wert, der größer oder gleich dem angegebenen Startwert ist, aber nicht den kleinsten solchen, es sei denn das Array ist wieder vorsortiert.

Da ich Norm zahlen suche habe ich das Array Bereits vor sortiert.

Hm, in dem Fall lässt sich die Komplexität wirklich auf O(log n) drücken, während die Implementierung so in O(n) liegt. Wenn du also sehr große Arrays hast, dann wäre es ratsam das noch zu optimieren (sprich eine Art BinarySearch zu implementieren).

Hallo onlinegurke,

BinarySerach muss man ja nicht selbst implementieren. Das gibt es ja schon als Methode.

herbivore

Jup, und da Array.BinarySearch ja sogar den Index des nächst größeren Elements zurückgibt (dann kodiert durch das bitweise Komplement), müsste ja folgendes gehen:

public int getNextBiggerNumber(int[] numbers, int x)
{
	int pos = Array.BinarySearch(numbers, x)
	if(pos < 0) // wenn das Element nicht direkt im Array enthalten ist, hol das nächst größere
	{
		pos = ~pos;
		if(pos == numbers.Length) //wenn es kein größeres gab
		{
			return 0;
		}
	}
	return numbers[pos];
}

beste Grüße
zommi

//Edit:
hab grad ~ (unären Bitkonverteroperator) mit dem ^(binäre xor-Operator) verwechselt. (nun korrigiert)
Evtl müsste man auch ne Exception schmeißen anstatt 0 zurückzugeben. (Vor allem wenn da auch negative Zahlen vorkommen).

Hm, das BinarySearch im Zweifelsfall das bitweise Komplement liefert ist mir noch nicht aufgefallen. Wieder was dazu gelernt. Ich war davon ausgegangen, dass alle Suchmethoden aus dem Framework immer -1 zurückgeben, wenn sie den gesuchten Wert nicht finden. Weil in dem Fall hätte man es nicht einsetzen können...