Binäre Suche ohne ohne Istgleich

[verzweifler (Gast)]

Hallo,
Ich zerbrech mir jetzt schon seit einer Stunde den Kopf über ein (denke 
ich) simples Problem:

Ich möchte aus dem Wertebereich 0x0 - 0xFF einen Wert suchen, aber die 
Funktion die ich zum Vergleichen benutze liefert mir nur True bei 
kleiner gleich und False bei größer.
Nun möchte ich natürlich mit möglichst wenig vergleichen zum Ziel kommen 
da die Vergleiche auf einem Embedded System (langsam) ablaufen.
Ich wollte die Binäre Suche Einsetzen, aber komm ums verrecken nicht auf 
eine Abbruchbedingung ohne einen Vergleich auf Gleichheit :(
Währe nett wenn mir da schnell jemand unter die Arme greifen könnte :)

[Mc (Gast)]

(a==b):
  (a<=b) && (b<=a)

[Test E. (test123)]

Tipp:

wenn y <= x und x <= y, dann ist x = y

[Peter II (Gast)]

a < b = true
b < a = true

a = b

[verzweifler (Gast)]

Danke schon mal für die Antworten! :)
Aber ich habe gerade einen Fehler in meiner Beschreibung entdeckt.
Ich kann nur folgenden Vergleich durchführen versuchter Wert < gesuchter 
Wert
Das heißt ich kann nur folgendes feststellen:
versuchter Wert < gesuchter Wert und versuchter Wert >= gesuchter Wert

Damit scheiden leider die obigen Vorschläge aus :(

[Peter II (Gast)]

verzweifler schrieb:
> Damit scheiden leider die obigen Vorschläge aus :(

warum kannst den vergleich nicht andersrum machen?

eigentlich geht das immer.

[verzweifler (Gast)]

Tja eigentlich schon aber in diesem Fall macht den Vergleich ein 
externes Gerät auf das ich keinen Zugriff habe :(
Ich möchte Daten auslesen, weiß aber nicht wie lang sie sind. Der 
Auslesevorgang kann beliebig wiederholt werden. Ich kann mit einem 
Kommando n bytes auslesen, aber wenn ich zu mehr auslesen will als 
vorhanden ist kommt ein Fehler. Jetzt möchte ich auf dem schnellsten Weg 
wissen wieviele Datenbytes vorhanden sind :)

[Peter II (Gast)]

Ich denke nicht das es da viele Möglichkeiten gibt.

einfach mit Maximum anfangen und denn weils entscheiden ob jeweil ok 
oder nicht. Dann wieder halbieren usw.

[verzweifler (Gast)]

Danke an alle für die Hilfe, vor allem um die Zeit :)

Ich bin jetzt mit dieser Lösung zufrieden:

int left = 0;
int right = 0xFF;
int gesucht = (left + right)/2;
    
while(true)
{
    gesucht = (left + right)/2;
    if(isOutOfRange(gesucht)) // gesucht < versucht
    {
        right = gesucht;
    }
    else // x >= gesucht
    {
        left = gesucht;
    }
    if(left == right)
    {
        return gesucht;
    }
}

Ist stark vereinfacht, sollte aber verständlich sein falls jemand das 
gleiche Problem hat.

[Logiker (Gast)]

Aber der Ansatz oben war doch gut.
Nur das er eben nicht mit <= sondern mit < ausgeführt werden muss

(a==b) : !((b<a) || (a<b))

wobei ! die Negation sein soll.

Das ist wie in der boolschen Logik. Mit einer Verknüpfung und der 
Negation kannst Du alle anderen zusammensetzen.

[Max H. (hartl192)]

Man könnte einen vergleich auch so machen:

if(!(a-b))
{

}

Wenn a == b ist das Ergebnis der Subraktion null, null negiert ist Wahr, 
sind sie ungleich ist das ergebnis ungleich null, und das negiert ist 
falsch.

[verzweifler (Gast)]

@Logiker und M.H.
Das Problem bei diesen Ansätzen ist das ich die Werte für a und b nicht 
kenne. Mein Problem ist eher so: Ich stell mir eine Zahl vor zwischen 0 
und 255, du musst sie erraten, ich sag dir aber nur ob deine Zahl größer 
ist als die die ich mir denke.

Hab den Code noch ändern müssen, er hat unter bestimmten Umständen 
Endlosschleifen produziert.

int left = 0;
int right = 0xFF;
int gesucht = (left + right)/2;
    
while(true)
{
    gesucht = (left + right)/2;
    if(isOutOfRange(gesucht)) // gesucht < versucht
    {
        right = gesucht;
    }
    else // x >= gesucht
    {
        left = gesucht;
    }
    if((left + 1) == right)
    {
        return left;
    }
}

[Amateur (Gast)]

Es liegt nun mal in der Natur von Vergleichen, dass es drei 
Möglichkeiten ("<", "=" oder ">")gibt.

Willst Du also alle erfassen, so brauchst Du zwei Vergleiche.

Kannst Du zwei Möglichkeiten zusammenfassen ("<=" oder ">=") so reicht 
natürlich ein Vergleich.

[Yalu X. (yalu) (Moderator)]

verzweifler schrieb:
> Hab den Code noch ändern müssen, er hat unter bestimmten Umständen
> Endlosschleifen produziert.

Du musst aber right mit 0x100 statt mit 0xFF initialisieren, sonst
funktioniert dein Code nicht für x=255.

Folgendes ginge ebenfalls, ist kürzer aber nicht ganz so flexibel wie
dein Code, da die mittlere Anzahl der benötigten Versuche nur dann
minimal ist, wenn die Größe des Suchraums eine Zweierpotenz ist:

  int gesucht=0, summand, versuch;

  for(summand = 128; summand; summand /= 2) {
    versuch = gesucht + summand;
    if(isInRange(versuch))
      gesucht = versuch;
  }
  return gesucht;

[Logiker (Gast)]

verzweifler schrieb:
> @Logiker und M.H.
> Das Problem bei diesen Ansätzen ist ...

Oh. Das habe ich überlesen,

Nun, Du scheinst ja eine Lösung zu haben. Aber etwas würde mich doch 
neugierhalber interessieren.

1. Wenn Du einen Wert unterhalb der gesuchten Länge versuchst, liefert 
die Gegenstelle einfach die Daten oder ist das ein gesonderter Befehl. 
(Deine Beschreibung hört sich nach ersterem an).
2. Sammeln sich in der Gegenstelle zu irgendwelchen Zeitpunkten immer 
mehr Daten an, oder löst Du das über einen dritten Befehl irgendwie aus?
3. Gibt es irgendwelche statistischen Auswertungen wieviele Daten über 
einen gewissen Zeitraum zur Verfügung stehen?

Ich meine es gäbe vielleicht effektivere Strategien. Aber wiegesagt, 
hauptsächlich bin ich neugierig.

[Läubi .. (laeubi)]

Logiker schrieb:
> Ich meine es gäbe vielleicht effektivere Strategien

z.B. gleich die ganze Aufgabenstellung/Arbeitsblatt zu posten ;-)

[Reinhard Kern (Gast)]

Hallo,

wenn v < g und v+1 >= g dann v == g

Gruss Reinhard

[WHAT? (Gast)]

Reinhard Kern schrieb:
> Hallo,
>
> wenn v < g und v+1 >= g dann v == g
>
> Gruss Reinhard

WHAT? v < g ergibt nach diversem Zauber (v+1 >= g) plötzlich g? Also 
irgendwas stimmt da nicht ;-).

[Logiker (Gast)]

Naja. Reinhard hat an sich schon Ahnung. Da ist wohl ein Hühnerbeinchen 
auf der Tastatur quer gelegen. :-)

[Reinhard Kern (Gast)]

WHAT? schrieb:
> Also
> irgendwas stimmt da nicht ;-).

Soll heissen: wenn v-1 < g und v >= g dann v = g

z.B. für g = 3:

v         1  2  3  4  5
v-1 < g   T  T  T  F  F
v >= g    F  F  T  T  T
                \
                 v=g

Glauben oder widerlegen.

Gruss Reinhard

[Karl H. (kbuchegg)]

Entweder so, wie Reinhard das geschrieben hat, oder

  wenn nicht( ( v < g ) oder ( g < v ) )
    dann sind sie gleich

(in anderen Worten: wenn keiner kleiner als der andere ist, dann müssen 
sie gleich sein)

oder

  wenn (( v >= g ) und ( g >= v ) )
    dann sind sie gleich

(in anderen Worten: wenn sowohl v größer/gleich g ist, als auch g 
größer/gleich v, dann ist keiner tatsächlich größer, sondern beide sind 
gleich).

Mit den genannten Vergleichen gibt es immer eine Möglichkeit, wie man 
'sind gleich' ausdrücken kann. Gegebenenfalls muss man eben 2 Vergleiche 
machen und die beiden kombinieren, um daraus seine Schüsse zu ziehen.

[Yalu X. (yalu) (Moderator)]

Karl Heinz schrieb:
> wenn nicht( ( v < g ) oder ( g < v ) )
>     dann sind sie gleich
> ...
> oder  wenn (( v >= g ) und ( g >= v ) )
>     dann sind sie gleich


Das Problem ist, dass man weder v<g noch v>=g hat. Im vorliegenden Fall
gibt es nur v<=g und die Negation davon, nämlich v>g (g ist dabei die
gesuchte Variable, auf die nicht direkt zugegriffen werden kann, und v
ist ein beliebiger Ausdruck). Siehe hier:

verzweifler schrieb:
> Ich möchte Daten auslesen, weiß aber nicht wie lang sie sind. Der
> Auslesevorgang kann beliebig wiederholt werden. Ich kann mit einem
> Kommando n bytes auslesen, aber wenn ich zu mehr auslesen will als
> vorhanden ist kommt ein Fehler.

Nach dem Muster von Reinhard kann man also die Gleichheit von v und g
mit v<=g && v+1>g feststellen, eine andere Möglichkeit gibt es nicht.

Dies wird in der vom verzweifler gefundenen Lösung implizit auch so
gemacht.

Wäre g übrigens keine ganze, sondern eine gebrochene Zahl mit unendlich
feiner oder unbekannter Auflösung, könnte man den nächstgrößeren
Nachfolger von v nicht bestimmen, so dass auch Reinhards Methode
versagt. Damit könnte in diesem Fall die Gleichheit mit den gegebenen
Operationen überhaupt nicht entschieden werden.

[Stefan (Gast)]

Ich habe dein Problem nicht genau verstanden aber vllt. könnte eine 
Lösung sein den Algorithnus des successive approximation ADCs in dein 
Programm einzubauen.

[Yalu X. (yalu) (Moderator)]

Stefan schrieb:
> aber vllt. könnte eine Lösung sein den Algorithnus des successive
> approximation ADCs in dein Programm einzubauen.

Das ist im Prinzip genau das, was der verzweifler hier gemacht hat:

  Beitrag "Re: Binäre Suche ohne ohne Istgleich"

Etwas deutlicher wird die Analogie vielleicht, wenn man in diesem Code

  Beitrag "Re: Binäre Suche ohne ohne Istgleich"

die arithmetischen Operationen durch entsprechende Bit-Operationen
ersetzt und die Namen entsprechend der Anwendung im ADC ändert:

  int adcErgebnis=0, bit, dacWert;

  for(bit = 0x80; bit; bit >>= 1) {             // alle 8 Bits nacheinander durchgehen     
    dacWert = adcErgebnis | bit;                // Bit versuchsweise setzen
    if(messwertIstGroesserOderGleich(dacWert))  // Mess- mit DAC-Spannung vergleichen
      adcErgebnis = dacWert;                    // ggf. Bit ins Ergebnis übernehmen
  }
  return adcErgebnis;

Genau so wird der ADC auch in Hardware realisiert. Im DAC-Register
(dacWert) werden – getrieben durch das Taktsignal und beginnend mit dem
höchstwertigen Bit – nacheinander alle Bits versuchsweise gesetzt und
die zu messende Spannung durch einen Analogkomparator mit der
Ausgangsspannung des DAC verglichen (messwertIstGroesserOderGleich). Je
nach Ergebnis des Vergleichs wird der Wert mit gesetztem Bit übernommen
(adcErgebnis = dacWert) oder der alte Wert mit nicht gesetztem Bit
stehen gelassen.

[verzweifler (Gast)]

Yalu X. schrieb:
> Du musst aber right mit 0x100 statt mit 0xFF initialisieren, sonst
> funktioniert dein Code nicht für x=255.

Danke, ist in der Tat bei mir falsch