algorithm - 二分探索コードの不等式を変更する

Question

すべきではない

if(a[mid] < t)return BS(mid+1,high);
else return BS(low,mid);

と同じ

if(a[mid] > t)return BS(low,mid-1);
else return BS(mid,high);

しかし、2 つ目は機能しません。

編集：つまり、コードが基本ケースに達していないということです。

Answer 1

mid を (low+high)/2 として計算する際には、整数除算を使用します。

Brefで。例によって

low = 3 、 high = 4 、a[3] >= t とする

したがって、BS(low,high) mid = (3+4)/2 = 3 #Integer_division を呼び出すことによって

a[mid] >=t なので、BS(low,high) と同等の BS(mid,high) を返します #infinite_loop

解決策はあなたの側で整数除算を使用するので、コードは次のようになります

if(a[mid] >= t)return BS(low,mid);
else return BS(mid+1,high);

これで問題が解決すると考えてください。