Teilen eines Feldes bei Divide et Impera Strategie

[TK1985]

Hallo zusammen!
Ich hab das Problem, dass ich nicht genau weiß wie ich in C bei einem rekursiven Divide et Impera Algorithmus (Maximum Subarray Problem, Binärsuche) ein gegebenes Feld in 2 Teilfelder zerlegen kann. Ich schaffe es zwar ein Feld in zwei Felder aufzuteilen, indem ich die erste Hälfte in Feld1 und die zweite Hälfte in Feld zwei kopiere, aber dabei ist unklar wie lang Feld1 und Feld2 ist.
Das sieht folgendermaßen aus:

int Feld1[500], Feld2 [500]

Feld1 = 1. Hälfte von Feld
Feld2 = 2. Hälfte von Feld

jetzt ruft die Funktion sich selbst auf: z.B. Suche(Feld1, start, end , Suchtext)

würde in Feld1 von start bis end nach Suchtext suchen. Nur wie bekomme ich heraus wie lange Feld1 ist und somit auch mein start und mein end?? Wenn ich die 1. und 2. Hälfte immer in vordefinierte Felder kopiere, haben die ja immer sie gleiche Länge. Feld1 und Feld2 ist immer 500 lang egal welche wieviele Elemente da wirklich drin stehen.
Die Länge brauche ich, da die Rekursion so lange durchgeführt wird bis in einem Feld nur noch 1. Element drin steht.
Hab mir schon Überlegt eine Struktur anzulegen und da als Komponente immer die tatsächliche Anzahl an Elementen reinzuschreiben.
Hab auch schon versucht gar keine neuen Felder anzulegen, sondern immer nur vom Ursprungsfeld auszugehen und start und end jeweils neu zu berechnen, hab da aber keine Berechnungsmöglichkeit gefunden.
Hat jemand eine Idee wie ich das mit dem Teilen hinbekomme?
Danke schon mal im Vorraus.

TK1985

[bullshit]

Also im unterricht haben wir zu dem Devide et Impera nur den algorithmus aufgeschrieben
void Select (int *A, int left, int right, int i, int * found)
{
int m; // Teiler-Position
if (right > left) {// falls Listenlaenge >= 2
m = Partition(A,left,right); // Liste aufteilen
if(i <= m – lef) // falls noch nicht gefunden
Select(A,left,m-1,i,found); // suche links weiter
else
Select(A,m,right,i-(m-left),found);
else
*found = A[left]; // gefundenes Item abliefern
}

vielleicht hilft dir das

[DarkTom]

@TK1985
Ich verstehe dich nicht ganz. Willst du jetzt binär suchen oder das Maximum Subarray Problem lösen? Falls letzteres, hast du bereits einen Alg. und weisst nur nicht, wie du ihn hinschreiben musst? Oder suchst du noch einen Algorithmus?
Falls du ihn bereits einen hast, erkläre ihn doch mal bitte.

[TK1985]

Zuerst muss ich das Maximum Subarray Problem implementieren und anschließend die Binärsuche. Das Prinzip mit dem Teilen ist bei beidem ja eigentlich gleich, nur das Terminierungskriterium unterscheidet sich.

Der Pseudocode zum Maximum Subarray Problem:

Funktion maxtSum (X)

wenn X enthält nur 1 Element a
dann
-----wenn (a > 0)
-----dann
----------maxtSum = a
-----sonst
----------maxtSum = 0
}
}
sonst
-----Teile X in A und B
-----maxTinA = maxtSum (A) //Hier müsste auch noch die start
und ende mit übergeben werden
-----maxTinB = maxtSum (B)
-----lMax = linkes Randmaximum von B
-----rMax = rechtes Randmaximum von A
-----maxtSum = Maximum von (maxTinA, maxTinB, rMax+lMax)
}

return maxtSum

[DarkTom]

Tut mir leid. Außer, dass bei beiden Algs die Eingabe geteilt wird, sehe ich kaum Gemeinsamkeiten. Aber vielleicht verstehe ich auch den Alg. einfach nicht. Die Randmaxima scheinen ja so vom Himmel zufallen?

Ich bin jetzt auch nicht genüpgend motiviert, um da im Netz nach zu suchen, was du meinen könntest. Nachdem mir ein linearer, nicht-rekursiver Algorithmus direkt ins Auge sprang als ich die Problemdefinition las, ist das Problem irgendwie uninteressant geworden.

Aber trotzdem noch eine Anmerkungen:
Du brauchst nichts kopieren, es reicht, wenn du die Grenzindizes in dem existierenden Array angibst. Vgl. dazu auch den Code von bullshit.