[C] ungleiches Array durchsuchen

KillerPinockel · 21. Oktober 2014

Hallo,

ich habe wirklich ein kleines Problem, aber ich komme einfach nicht drauf.

Eigentlich möchte ich ein Array nach einem Wert durchsuchen, der aber eventuell nicht genau drin vorkommt. Dann soll der am nächstliegendste Wert genommen werden. Problem ist aber, dass das Array bzw deren Werte nicht sortiert ist.
Ich hätte gedacht, dass ich eine Differenz bilde und dann schaue, welcher Wert dem gesuchten am nächsten kommt und diesen dann nehme, nachdem ich das gesamte Array abgesucht habe.

Leider komm ich wirklich auf keinen Code, der dieses simple Problem löst.

Ich hoffe ich könnt mir dabei kurz helfen

Danke!

Blublah · 21. Oktober 2014

Du vergleichst die bisher niedrigste Differenz mit der aktuellen Differenz. Wenn die neue Differenz niedriger ist, dann nimmst du den Wert. Starten tust du mit einer maximalen Differenz.

Modin666 · 21. Oktober 2014

z.B. mit einem Suchwert von 3 und array a und in c geschrieben:

double wert=3.0;
double diff=1000000000.0;
double a[N_max]={...<some values>...};
double ergebnis;

for(int i=0;i<N_Max; i++){
if(abs(a-wert)<diff) {
ergebnis= a;
diff=abs(a-wert);
}

PS: Meine Frau zieht mir gerade die Ohren lang. Besser ist es, wenn du die Liste vorsortierst, was den Rechenaufwand angeht. Wenn dir das egal ist, sollte der Code oben reichen. Für kleines N_max ist das eh recht egal.

wahli · 21. Oktober 2014

Ich sehe das Problem nicht. Wozu soll eine Sortierung gut sein?
Beschreibe doch erstmal deine Ansätze.

Und mach mal ein Beispiel. Vermutlich geht es um Zahlen, oder?

S.Kara · 21. Oktober 2014

Logik:
Sei x das zu druchsuchende Array, y die Nummer des Elements das am nächsten am Wert liegt und z der Wert nach dem du suchst.

Code:

y = 0;

for (int i = 1; i < Länge von x; i++) {
    if (x[i] == z) break; // genaue Übereinstimmung gefunden
    if (abs(x[i] - z) < abs(x[y] - z)) {
        y = i;
    }
}

Modin666 · 21. Oktober 2014

stimmt, Abbruch hab ich vergessen

asdfman · 21. Oktober 2014

wahli schrieb:
Ich sehe das Problem nicht. Wozu soll eine Sortierung gut sein?

Weil man dann eine binäre Suche machen kann. Möglicherweise kommt das aber aufgrund irgendwelcher Umstände nicht in Frage. OP ist ja etwas sparsam mit Details.

wahli · 21. Oktober 2014

asdfman schrieb:
Weil man dann eine binäre Suche machen kann. Möglicherweise kommt das aber aufgrund irgendwelcher Umstände nicht in Frage. OP ist ja etwas sparsam mit Details.

Sorry, ich hatte mich unverständlich ausgedrückt. Ich kenne die Vorteile der Sortierung bei einer Suche, aber ich wollte es vom TE wissen. U. U. ist eine Sortierung und anschließende Suche langsamer als eine direkte Suche ohne Sortierung.

TrebuTurbo · 21. Oktober 2014

wahli schrieb:
Sorry, ich hatte mich unverständlich ausgedrückt. Ich kenne die Vorteile der Sortierung bei einer Suche, aber ich wollte es vom TE wissen. U. U. ist eine Sortierung und anschließende Suche langsamer als eine direkte Suche ohne Sortierung.

Bei so einer einfache Suche bringt eine Sortierung nix. Die effizientesten Suchalgorithmen brauchen im Durchschnitt n * log(n) Schritte bei n Feldelementen. Hier, wie von S.Kara beschrieben, braucht man sogar im Worst-Case nur n Schritte.

S.Kara · 21. Oktober 2014

Da der TE schon mit der von ihm genannten Aufgabe überfordert ist, wird er für eine Binäre Suche wohl noch nicht bereit sein.

Ich tippe einfach mal darauf, dass es sich um eine Aufgabe aus der (Hoch-)Schule handelt und die unsortierte Liste einfach vorgegeben ist.

daemon777 · 22. Oktober 2014

TrebuTurbo schrieb:
Bei so einer einfache Suche bringt eine Sortierung nix. Die effizientesten Suchalgorithmen brauchen im Durchschnitt n * log(n) Schritte bei n Feldelementen. Hier, wie von S.Kara beschrieben, braucht man sogar im Worst-Case nur n Schritte.

Wenn die Menge der Zahlen allerdings gleich bleibt und ich öfter suchen muss sieht der Fall wieder anders aus. Bei einer Suchanfrage pro Sortierung gebe ich dir allerdings recht.

TrebuTurbo · 23. Oktober 2014

daemon777 schrieb:
Wenn die Menge der Zahlen allerdings gleich bleibt und ich öfter suchen muss sieht der Fall wieder anders aus. Bei einer Suchanfrage pro Sortierung gebe ich dir allerdings recht.

Ja klar, natürlich. Hatte nur daran gedacht ein bestehende Feld genau einmal zu durchsuchen.

Suche

[C] ungleiches Array durchsuchen

KillerPinockel

Lieutenant

Blublah

Lt. Commander

Modin666

Lieutenant

wahli

Admiral

S.Kara

Captain

Modin666

Lieutenant

asdfman

Commander

wahli

Admiral

TrebuTurbo

Cadet 3rd Year

S.Kara

Captain

daemon777

Lt. Commander

TrebuTurbo

Cadet 3rd Year

Ähnliche Themen