binäre Suche

[Mariexshhx]

Wenn ich die Funktion f (x) = 4 log2 x − 4 für x ∈ {1, . . . , 99} habe ? Ist es dann möglich mit binärer Suche die Nullstelle zu finden? Ich denke nein, weil man ja irgenwann als Mitte 25,5 hat und dies liegt nicht in der Menge ? Wird hier immer genau die Mitte genommen oder ist es doch möglich ?

 

[httpdigest]

Wenn ich die Funktion f (x) = 4 log2 x − 4 für x ∈ {1, . . . , 99} habe ? Ist es dann möglich mit binärer Suche die Nullstelle zu finden?

Ja. Die Funktion ist ja streng monoton steigend. Du musst halt nur an zwei Stellen anfangen (links und rechts) mit unterschiedlichen Vorzeichen.
Intervallsuche wäre aber besser.

 

[KonradN]

Wenn ich die Funktion f (x) = 4 log2 x − 4 für x ∈ {1, . . . , 99} habe ? Ist es dann möglich mit binärer Suche die Nullstelle zu finden? Ich denke nein, weil man ja irgenwann als Mitte 25,5 hat und dies liegt nicht in der Menge ? Wird hier immer genau die Mitte genommen oder ist es doch möglich ?

Ich frage mich gerade, was Dein Problem mit 25,5 ist? Wenn x nur ganze Zahlen annehmen kann, dann wäre die Berechnung des neuen Wertes ja immer eine Integer Operation. Und damit wäre die Nachkommastelle abgeschnitten.

Ansonsten bei sowas einfach einmal alle Werte berechnen und in ein Array eintragen. Dann sieht man schnell:

• sind die Zahlen sortiert?
• ist der gesuchte Wert vorhanden?

==> Dann hast Du es sozusagen auf das abgeleitet, das Du ja schon kennst: Suche in einem sortierten Array.

(Mit etwas Mathe-Wissen sieht man das aber schnell ... log2(2) ist 1 und damit hat man 4-4 = 0. Und die log(x) ist - wie @httpdigest schon schrieb - streng monoton steigend....)

 

[Mariexshhx]

Ich frage mich gerade, was Dein Problem mit 25,5 ist? Wenn x nur ganze Zahlen annehmen kann, dann wäre die Berechnung des neuen Wertes ja immer eine Integer Operation. Und damit wäre die Nachkommastelle abgeschnitten.

Ansonsten bei sowas einfach einmal alle Werte berechnen und in ein Array eintragen. Dann sieht man schnell:

• sind die Zahlen sortiert?
• ist der gesuchte Wert vorhanden?

==> Dann hast Du es sozusagen auf das abgeleitet, das Du ja schon kennst: Suche in einem sortierten Array.

(Mit etwas Mathe-Wissen sieht man das aber schnell ... log2(2) ist 1 und damit hat man 4-4 = 0. Und die log(x) ist - wie @httpdigest schon schrieb - streng monoton steigend....)

ich wunder mich halt nur, weil mir einmal diese Frage mit dem Intervall [1,99] und einmal mit der Menge {1,....,99} gestellt wurde und ich dachte mit der Menge geht es nicht, weil die 25,5 nun mal nicht in der Menge liegt mit dem Intervall würde die Suche natürlich klappen

 

[Mariexshhx]

Ja. Die Funktion ist ja streng monoton steigend. Du musst halt nur an zwei Stellen anfangen (links und rechts) mit unterschiedlichen Vorzeichen.
Intervallsuche wäre aber besser.

Die Frage wurde auch einmal mit Intervallsuche gestellt, deswegen habe ich mich dann gefragt, ob es mit der Menge überhaupt klappt