改变不平等的二进制搜索代码

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

在Bref。作为示例

让低= 3，高= 4，[3]> = T

所以通过调用BS（低，高） MID =（3 + 4）/ 2 = 3 #Integer_division

由于[MID]> = T所以返回BS（中，高），其等效于BS（低，高）#infinite_loop

将溶液使用整数除法在你身边因此，代码应该是这样

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

认为这将解决您的问题。