更改二进制搜索代码中的不等式

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

但是第二个不起作用，为什么？

编辑：我的意思是不起作用，代码没有达到基本情况。

Answer 1

在计算mid为（低+高）/2时，它使用整数除法。

在布雷夫。举例来说

设低=3，高=4，a[3]>=t

所以通过呼叫BS（低、高）mid=（3+4）/2=3#Integer_division

由于a[mid]>=t因此返回BS（mid，high），其等效于BS（low，high，low）#infinite_loop

解决方案在您的一侧使用整数除法，因此代码应该像一样

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

我想这会解决你的问题。