バイナリ検索を実行する

Question

私はバイナリ検索を実行しています。の値がtrueとなるように、最小値がxであることが必要です。 black_box(x)はその後、私のx+1,x+2,x+3,x+4....upto infintyを真を与える場合

black_box(x)

• のプロパティはすべて、これは単純なバイナリ検索

  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; 
  } 
  

  何私の場合です整数値のために私にtrue

を与えますが欲しい小数点以下2桁の整数です。バイナリ検索はどのように行うべきですか？

Answer 1

startとendの間は、0.01と異なるだけです。だから、停止条件は今ある：あなた自身をコメントに指定されている

while(end-start > 0.01){ 

はさらに、あなたは、インデックスが離散しないので、あなたのアルゴリズムでstartとendをデクリメント/インクリメントすることはできません。完全なアルゴリズムは以下のようになります。

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; 
} 

これが機能する各反復startで低いため、正確な値にを結合させ、endは、正確な値に上限です。両方とも0.01を超えていない場合は、startとendの間の範囲にあり、その差は0.01未満であるため、2小数点以下であることがわかります。

しかし、あなたのアルゴリズムはend = Infに設定することでこれではうまくいかないという意味では間違っています。おそらく、表現可能な最大値を使用するか、指数関数的なインクリメント検索を前処理ステップとして使用することができます。