binäre Suche im Intervall

M

Mariexshhx

Bekanntes Mitglied
f (x) = 4 log2 x − 4 für x ∈ [1, 99]. Ist es möglich die Nullstellen dieser Funktion im gegeben intervall zu finden ? Ich hätte gesagt nein,weil die binäre Suche läuft ja über die Indexe also wöre Index 0 dann die 1 und Index 98 dann die 99. Doch was passiert wenn rechts und links neu gesetzt werden. Das kann doch nicht gehen weil die Zahlen ja keinen direkten Nachfolger haben. Das intervall ist zwar endlich, aber überabzählbar. Ich hoffe man konnte verstehen was ich meine. Kann mir dort jemand weiterhelfen ? Danke im vorraus 🙂
 
httpdigest hat gesagt.:
Duplikat von: https://www.java-forum.org/thema/binaere-suche.199565/
Zum Vergrößern anklicken....
Nicht ganz - das dürfte die Fortsetzung sein, nachdem die Fragestellung mit Interval vs. Menge nicht beantwortet wurde (vermute ich)

Ich muss gestehen, dass ich Probleme habe, Dich zu verstehen. Das war aber auch schon beim anderen Thread so, als Du anfingst mit Menge und Intervall.

Das Problem ist, dass hier Begriffe verwendet werden, die so nicht gut definiert sind. Binäre Suche ist ein Verfahren, um bei einer Menge von (sortierten) Elementen sehr effektiv ein Element zu finden (oder eben nicht, wenn es nicht da ist).
Oder nach Wikipedia:
Die binäre Suche ist ein Algorithmus, der auf einem Feld (also meist „in einer Liste“) sehr effizient ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert.
Zum Vergrößern anklicken....

Gegeben ist bei Dir aber eine Funktion (die hat erst einmal unendlich viele Elemente. Und zwischen zwei ungleichen Elementen hast Du immer wieder unendlich viele Elemente!)
Wenn Du eine Menge hast von Elementen für x, dann entsteht daraus eine klare Menge von Werten -> die binäre Suche wäre hier anwendbar.

Bei dem Intervall hast Du das aber nicht. Und da kann es dann prinzipiell sein, dass Du unendlich rechnest und nie zu dem Ergebnis kommst.

Der "Abstand" wird mit jeder Rechnung aber halbiert. Einfaches Beispiel:
Wir haben als untere Grenze x, diese Grenze x sei unsere Nullstelle. obere Grenze ist x+d. Wir prüfen also x+d/2, welches zu groß ist, daher haben wir die Grenzen x und x+d/2.
Das gleiche Spielchen, obere Grenze wird zu x+d/4, dann x+d/8, .... Du wirst nie x erreichen. Aber wer gut aufgepasst hat, der merkt hier auch: Das ist nicht die binäre Suche, wie wir diese sonst durchführen:
Die neue Grenze ist eben nicht der geprüfte Wert sondern eben ein Wert daneben!.
Also bei "12345" und ich suche die 2: Erste Grenzen sind 1 und 5 - > ich schaue bei der 3
Da der Wert zu hoch ist, suche ich nun mit den Grenzen 1 und 2 (und nicht 3 sondern 3-1!)
 
KonradN hat gesagt.:
Nicht ganz - das dürfte die Fortsetzung sein, nachdem die Fragestellung mit Interval vs. Menge nicht beantwortet wurde (vermute ich)

Ich muss gestehen, dass ich Probleme habe, Dich zu verstehen. Das war aber auch schon beim anderen Thread so, als Du anfingst mit Menge und Intervall.

Das Problem ist, dass hier Begriffe verwendet werden, die so nicht gut definiert sind. Binäre Suche ist ein Verfahren, um bei einer Menge von (sortierten) Elementen sehr effektiv ein Element zu finden (oder eben nicht, wenn es nicht da ist).
Oder nach Wikipedia:


Gegeben ist bei Dir aber eine Funktion (die hat erst einmal unendlich viele Elemente. Und zwischen zwei ungleichen Elementen hast Du immer wieder unendlich viele Elemente!)
Wenn Du eine Menge hast von Elementen für x, dann entsteht daraus eine klare Menge von Werten -> die binäre Suche wäre hier anwendbar.

Bei dem Intervall hast Du das aber nicht. Und da kann es dann prinzipiell sein, dass Du unendlich rechnest und nie zu dem Ergebnis kommst.

Der "Abstand" wird mit jeder Rechnung aber halbiert. Einfaches Beispiel:
Wir haben als untere Grenze x, diese Grenze x sei unsere Nullstelle. obere Grenze ist x+d. Wir prüfen also x+d/2, welches zu groß ist, daher haben wir die Grenzen x und x+d/2.
Das gleiche Spielchen, obere Grenze wird zu x+d/4, dann x+d/8, .... Du wirst nie x erreichen. Aber wer gut aufgepasst hat, der merkt hier auch: Das ist nicht die binäre Suche, wie wir diese sonst durchführen:
Die neue Grenze ist eben nicht der geprüfte Wert sondern eben ein Wert daneben!.
Also bei "12345" und ich suche die 2: Erste Grenzen sind 1 und 5 - > ich schaue bei der 3
Da der Wert zu hoch ist, suche ich nun mit den Grenzen 1 und 2 (und nicht 3 sondern 3-1!)
Zum Vergrößern anklicken....
und bei deinem Beispiel kommt es ja zu einem Problem wenn ich in dem Intervall Suche, denn wie du sagst ich suche dann nicht mit der Mitte als Grenze weiter, sondern mit der Mitte-1 bzw. Mitte+1. Wenn ich nun, aber ein Intervall von [1,99] habe, dann gibt es doch nie einen direkten Nachfolger und man weiß nicht wie die Grenzen neu gesetzt werden sollen oder funktioniert das doch ?
 
KonradN hat gesagt.:
Nicht ganz - das dürfte die Fortsetzung sein, nachdem die Fragestellung mit Interval vs. Menge nicht beantwortet wurde (vermute ich)

Ich muss gestehen, dass ich Probleme habe, Dich zu verstehen. Das war aber auch schon beim anderen Thread so, als Du anfingst mit Menge und Intervall.

Das Problem ist, dass hier Begriffe verwendet werden, die so nicht gut definiert sind. Binäre Suche ist ein Verfahren, um bei einer Menge von (sortierten) Elementen sehr effektiv ein Element zu finden (oder eben nicht, wenn es nicht da ist).
Oder nach Wikipedia:


Gegeben ist bei Dir aber eine Funktion (die hat erst einmal unendlich viele Elemente. Und zwischen zwei ungleichen Elementen hast Du immer wieder unendlich viele Elemente!)
Wenn Du eine Menge hast von Elementen für x, dann entsteht daraus eine klare Menge von Werten -> die binäre Suche wäre hier anwendbar.

Bei dem Intervall hast Du das aber nicht. Und da kann es dann prinzipiell sein, dass Du unendlich rechnest und nie zu dem Ergebnis kommst.

Der "Abstand" wird mit jeder Rechnung aber halbiert. Einfaches Beispiel:
Wir haben als untere Grenze x, diese Grenze x sei unsere Nullstelle. obere Grenze ist x+d. Wir prüfen also x+d/2, welches zu groß ist, daher haben wir die Grenzen x und x+d/2.
Das gleiche Spielchen, obere Grenze wird zu x+d/4, dann x+d/8, .... Du wirst nie x erreichen. Aber wer gut aufgepasst hat, der merkt hier auch: Das ist nicht die binäre Suche, wie wir diese sonst durchführen:
Die neue Grenze ist eben nicht der geprüfte Wert sondern eben ein Wert daneben!.
Also bei "12345" und ich suche die 2: Erste Grenzen sind 1 und 5 - > ich schaue bei der 3
Da der Wert zu hoch ist, suche ich nun mit den Grenzen 1 und 2 (und nicht 3 sondern 3-1!)
Zum Vergrößern anklicken....
also würden sie sagen die binäre Suche funktioniert in der Menge {1,....,99}, aber nicht im Intervall [1,99]?
 
Mariexshhx hat gesagt.:
und bei deinem Beispiel kommt es ja zu einem Problem wenn ich in dem Intervall Suche, denn wie du sagst ich suche dann nicht mit der Mitte als Grenze weiter, sondern mit der Mitte-1 bzw. Mitte+1. Wenn ich nun, aber ein Intervall von [1,99] habe, dann gibt es doch nie einen direkten Nachfolger und man weiß nicht wie die Grenzen neu gesetzt werden sollen oder funktioniert das doch ?
Zum Vergrößern anklicken....
Du kannst dann nur die Stelle, die Du geprüft hast, als Grenze nehmen. Aber das ist streng genommen keine binäre Suche mehr!

Was wir hier haben ist ein mathematisches Annäherungsverfahren - da gibt es auch diverse Möglichkeiten / Optionen. Ein Beispiel wäre das Newtonsche Näherungsverfahren: https://de.serlo.org/mathe/1989/newtonsches-näherungsverfahren
 

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Lineare Suche / Binäre Suche
Antworten: 2
Array, lineare Suche, binäre Suche, Programm bleibt unerwartet stehen...
Antworten: 6
Binäre Suche mit Comparator
Antworten: 5
Binäre Suche
Antworten: 6
binäre Suche
Antworten: 4

Zurück
Oben