Durchführen einer binären Suche

Question

Ich bin eine binäre Suche ausführen, sagen wir, ich muss den Mindestwert von x so finden, dass black_box(x) gibt mir true Ergebnis.

Eigentum von black_box(x)

• Wenn black_box(x) mich wahr gibt dann x+1,x+2,x+3,x+4....upto infinty alles gibt mir true

Für Integer Wert diese binäre Suche einfach

start=0; 
end = Max; 
ans=-1; 
while(start<=end){ 

    mid =(start+end)/2; 
    if(black_box(mid)): 
     end =mid-1 
     ans=mid; 
    else: start=mid+1; 
} 

Was ich, wenn will ein floating point Ganzzahl bis 2 Dezimalstellen, wie soll ich binäre Suche durchführen?

Answer 1

Sie iterieren einfach bis start und end unterscheiden sich nicht mehr als 0.01. So ist die Stoppbedingung jetzt:

while(end-start > 0.01){ 

Darüber, wie Sie in der Kommentar selbst angegeben haben, können Sie nicht/Abnahme erhöhen start und end in Ihrem Algorithmus, da die Indizes nicht diskret sind. Der vollständige Algorithmus ist jetzt:

start=0; 
end = Max; 
ans=-1; 
while(end-start > 0.01){ 

    mid =(start+end)/2.0; 
    if(black_box(mid)): 
     end =mid 
     ans=mid; 
    else: start=mid; 
} 

Dies funktioniert, weil bei jeder Iteration start a untere Grenze auf den genauen Wert und end eine obere Schranke auf den genauen Wert ist. Wenn beide nicht mehr als 0.01 abweichen, wissen wir, dass es im Bereich zwischen start und end liegt und da der Unterschied weniger als 0,01 beträgt, ist es genau zwei Dezimalstellen.

Trotzdem ist Ihr Algorithmus in dem Sinne falsch, dass Sie mit end = Inf nicht arbeiten können. Sie können möglicherweise den maximal darstellbaren Wert verwenden oder die exponentielle Inkrementsuche zuerst als Vorverarbeitungsschritt verwenden.