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 它使用整数除法。

在简介中。举例说明

令低 = 3 , 高 = 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);

认为这会解决您的问题。