Java Binary Search zum Berechnen einer Distanz

[xxhagixx]

Hallo Leute,
ich sitze hier gerade an einer älteren Aufgabe, die ich gerne lösen möchte.
Als Eingabe bekomme ich die Werte a,b,c,d wobei a eine Distanz zw.(einschließlich) 0 und a ist, b ist eine Anzahl von Markierungen die auf der Strecke verteilt werden müssen bis auf einer Lücke zwischen (ausschließlich)c und d.
Als Ergebnis gibt es dann die maximale minimum Distanz zw. den einzelnen Markierungen.
Als Beispiel wäre da z.B. a = 8, b = 2, c = 3, d = 7 mit dem Ergebnis 8. Noch Eins: a = 8, b = 5, c = 1, d = 3 mit dem Ergebnis 1,666666...
Ich habe es soweit mit binarySearch versucht um die Näherungswerte zu berechnen, bekomme allerdings nicht die gewünschten Ergebnisse.

public double binarySearch(double low, double high, int c, int length) {//low = 0, high = a+1, length = a -(d-c+1)
        if (high < low) {
            return -1;
        } else {
            double mid = low + ((high - low) / 2);
            double calc = mid * c;
           
    
            if (calc > length) {
              return binarySearch(low, mid, c, d);
            } else if ((length - calc) > Math.pow(10, -4)) {//Tolerance 0.0001
                System.out.printf("E is %f\n", (length - calc));
               return binarySearch(mid, high, c, d);
            } else {
                return mid;
            }
        }
    }

Ich vermute das Problem liegt darin, dass das einschließende, ausschließende nicht beachtet wird, stehe aber auch gerade irgendwie auf dem Schlauch, vielleicht kann mir ja jemand von euch helfen.
Danke schonmal

 

[hroessler]

Hallo,
bitte entschuldige. Ich verstehe ehrlich gesagt 0 was du gerne tun möchtest. Liegt aber evtl. auch am Begriff "Binary Search". Denn Binary Search ist ein Algorithmus zum schnellen suchen innerhalb von Index basierten, bereits sortierten Collections und hat mit einem Näherungsverfahren nix zu tun.

Sicher dass du nicht eher Algorithmen aus der Statistik benötigst?

greetz
hroessler

 

[titanskin]

Es gibt den Begriff außerhalb von Index-basierten Listen. Viele Algorithmen nutzen ihn um einen Wert mit einem Art Entscheider zu suchen.

Allerdings ist dort der Aufbau etwas anders.

Schon der Satz
a eine Distanz zw.(einschließlich) 0

verwirrt mich.

Du willst den Index der Markierung raus bekommen? Die Markierungen sind gleichmäßig Verteilt, außer im ausgenommenen Intervall. Verstehe ich das richtig? Das geht wesentlich einfacher . Überlege mal.

 

[xxhagixx]

@ hroessler
Also die Funktion und die Herangehensweise ist schon sehr ähnlich, kann aber auch tatsächlich sein das man es dann anders benennt. Aus der Statistik wird hier glücklicherweise nichts gebraucht.

Also um es mal anders zu Beschreiben. Ich will die maximal mögliche Distanz zwischen den Markierungen berechnen.
So könnte man die 2 Markierungen im ersten Beispiel irgendwo in [0,3] und [7,8] verteilen, allerdings wäre das dann nicht die mögliche maximale Distanz, die ist nämlich dann gegeben wenn die Markierungen bei 0ten und 8ten Streckenabschnitt sind. Womit die Distanz zwischen den Markierungen 8 ist und somit maximal.
Ich hoffe es ist jetzt verständlicher.

Und Ja ich stehe gerade total auf dem Schlauch...

 

[The Ripper]

ich verstehs leider auch nicht

 

[FreddyMercury]

Warum willst du eine BinarySearch dafuer benutzen? Ich glaube ich verstehe was du machen moechtest, aber Binary search ist divide-and-conquer, also du halbierst mit jedem schritt die Suche. Das macht die Suche nach der Distanz ein wenig schwerer. Wenn du den Tree zwei mal durchsuchst kannst du die Distanz eher rausfinden, aber das frisst dann wieder CPU. Korrigier mich jemand wenn ich hier falsch liege.

 

[Zespire]

Solange C! =0 ist und D != A ist die maximale Distanz = A. (In dem Fall kannst du immer einen Punkt bei 0 und A haben)

Für den Fall das C= 0 ist ist die maximale Distanz = A-D.( 0 ist blockiert also verschiebt sich der erste wert nach D)

Für denn Fall das D = A ist ist die maximale Distanz = C.(A ist blockiert also musst du bei C ansetzen)

Und wozu brauchst du mehr als zwei Punkte?