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

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

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

Answer 1

在将 mid 计算为 (low+high)/2 时，它使用整数除法。

在布雷夫。举例

让 low = 3 , high = 4 , a[3] >= t

所以通过调用 BS(low,high) mid = (3+4)/2 = 3 #Integer_division

由于 a[mid] >=t 所以返回 BS(mid,high) 相当于 BS(low,high) #infinite_loop

解决方案使用你身边的整数除法所以代码应该像

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

认为这将解决您的问题。